If a mage with Premonitions sees he is going to be visited by another mage later that day, does that count as Scrying?
Would Premonitions need to Penetrate the visiting magus' Parma Magica?
I doubt, that Premonitions (ArMDE p.170) provides a precise insight like "he is going to be visited by another mage later that day". You only can
intuitively sense whenever something is wrong, or is likely to go wrong
soon.
So it at least requires an enormous amount of deduction or paranoia, to conclude from such an intuition that you are "visited by another magus later that day".
So the Premonitions certainly did not scry on that other magus - but his conclusion still makes that magus highly suspect. Why is he that much focused on or in fear of that other magus? 
I think Premonitions is like Second Sight, and doesn't need to penetrate.
If you are in a Wizard War with someone, or are feuding with them, I think Premonitions could give you a bad feeling that they were about to move against you. Is that Scrying? Probably not, unless you've really annoyed the Quaesitors, given it's basically involuntary. But someone could claim that and make you defend yourself.
I understand Scrying to require an act of will and magic. Premonitions have always seemed imposed (involuntary) and don't necessarily involve magic. Thus, not a Hermetic crime.
It's a little unclear to me how voluntary premonitions are. (They haven't come up in a game I've been in so this may be a Your Mileage May Vary situation.
his Ability can be called upon by you or the storyguide, as appropriate, whenever there is a chance to avoid danger. -AMDE
While a player might be able to do use this voluntarily, I don't know if that implies a character can do this. However, given that it is an ability, and abilities can be trailed and taught and all that, a character can presumably get better at it on purpose, and there's nothing that I can see (on a quick google) saying that a person with Premonitions can't Practice them, which to me suggests that they can, in theory, be voluntary (even if the only way to make them voluntary is to put yourself into dangerous situations on purpose.)
Also,
If you beat the Ease Factor by 3 or more, you also get some sense of the nature of the danger, with more detail if you roll more highly.
So on a roll of 9 against an EF 9, you might get a sense of danger; on a roll of 12 you might get 'A dangerous person' and on a 15 you might get 'A mage with hostile intent' or 'A danger that comes with a storm' which puts you on guard against a mage who seems overly polite, or a visitor who shows up while it's raining.
Anyway all this to say, assuming a character can (find a way to) intentionally trigger a premonition AND that the character rolls high enough, they could in very specific circumstances be gathering information about a fellow mage, which as Tomaso suggests is probably only a problem if you've really annoyed the Quaesitors. That said, given that Scrying is one of the more harshly penalized breeches of the code, if a mage was known to be doing constant Premonition Crunches, gathering all the books they can find on the matter and routinely trying to win at The Lady or the Tiger, someone might pre-emptively call the matter before a Tribunal to hash it out in advance.
Coda, TMRE has some notes on Divination and Scrying, I think at this point it strays into that territory.
I think the better question is whether premonitions could be mistaken for or lead to charges of scrying. after all it isn't like the tribunal is making decisions based on the game rules...
If a magus swears under magic that they have premonitions, and did not seek to have information about that maga who was out to harm him but was sent a warning from a mysterious power, I think it will get a pass.
Generally. I mean if someone is looking for an excuse to come after them, it will probably do...
I think it makes the story better so the answer is Yes.
I like to assign a Patron to these powers. Is your power a gift of a powerful Fey such as the pagan gods or a divine intervention gift from God? Maybe it is a gift from a genius Loci or a Dragon? Dare I say Demon?
Penetration is almost irrelevant for all these creatures as they have very high penetration scores... especially God. Do demons really need to penetrate for them to give you a vision?
Each has a reason for the premonitions and the triggers are not the same. If you press for a specific premonition, they might give one to you or not.
Keep in mind that not all scying is equal under the hermetic law and not even equal across tribunals
- Premonition is accidental and does not reveal any magical secrets = No intent, no Damage = Trivial case
- Premonition is intentional but does not reveal any magical secrets = Mostly trivial but may be awarded some penalty
- Premonition is intentional and reveals magical secrets = potentially a Wizard's March case. Defender will have to prove he suspected foul play.
W