Yes, that's the gist of it. The people in this universe seem to have a very narrow understanding of what "magic" is, since they've got it sorted in three categories (to wit: pandemonium, free magic, magic potential), we've found out that pandemonium magic at least relies on a bound spirit (dunno about free and potential), and there's this "black crystal" McGuffin that blocks out magic.
But there's plenty of clearly-not-mundane skills (such as Tobi's blueprint-o-vision, no matter how much she insists it's totally normal, or the Paladin's grafted cells) that are technically not "magic" as far as it is understood in universe, but which clearly looks magical to us readers.
Or to go back to everyone's favorite Levin, we know he participated in Death Run and similar games, and that Death Run contestants are made to black crystal necklace to block their magic. It doesn't block Tobi's abilities, and presumably neither did it block Levin's. The Paladin didn't detect anything about Levin nor about Tobi. And of course, there's Burk, who's not using magic either, and yet is still absolutely ridiculous in combat. The Royal Guards also exhibit clearly supernatural speed and strength, and that can't just be chalked up to "training from birth".
And to be honest, Pablo's outfit is clearly weird, too.
Then if we take the recent intermission into account, we can hazard the guess that "magic" is understood as supernatural powers that originate from an alternate dimension (let's call it Pandemonium, as it has to be the home plane of those spirits of Pandemonium) trying to infiltrate the HOH world (perhaps to escape some unknown threat), but other supernatural powers (perhaps those "native" to the world instead of originating from Pandemonium) are not considered to be magic.
So if we accept that "magic" has a very narrow definition in this universe which doesn't encompass all sorts of supernatural abilities, then yes, it's perfectly reasonable to accept that Veda is indeed not a magic user. She still has weird powers, that much is indisputable.
In fact it's a bit surprising that the magical-but-not-magic thing is not more widely known, given freaks like Levin or Burk, Global Order bioweapon programs, or Livarian diplomatic couture.
Fun fact from re-reading: Herman and Sherman.