Thing is, there are a huge number of ways that skillshots, even fast ones, can go awry before they reach the target, and many of them are zero-counterplay. The most commonly encountered in lane trading is the forward blink (where the enemy goes over the projectile.) Many common mids have the ability to do this often. Kat, Zed, Talon, and LeBlanc being a few just off the top of my head.
If they engage at exactly the same time (or a split second afterwards) you go to harass, they win hands-down. This means that even when Q might not be so devestating against certain match-ups, it's even easier to counterpick Veigar than it was before, which was honestly just pick Fizz or Talon and laugh all the way to the bank. Veigar's counters are among the hardest counters I've ever encountered in League.
I'm not necessarily willing to dismiss the possibility that many skillshots are too hard to land. I think this game would probably benefit from more targeted damage, given that it makes mobility less overwhelming. I honestly wish mana meant more for a champion too. That strategic play made the earlier League of Legends very satisfying to play. It was more cerebral and less twitch. Trades were more intentional and calculated. Less uncertainty about spending abilities made the game more like a chess match. Most champions had resources and they mattered.
But specifically Veigar suffers a lot from being a squishy champion with no mobility that can't reliably trade in lane. He makes one mistake and gets crushed by many common mids. He has to rely on his only (arguably) defensive skill in order to have a chance at combo-ing. I've seen him four times since the "buff" and three of those he was support. And the mid fed.
Meanwhile Annie's targeted damage stuns, Vlad's targeted damage heals him, and LeBlanc's targeted damage is supplemented by excellent mobility. Veigar is in a rough spot, and no small part of this is the state of his Q.