Believe it or not, flashjeff, not all of the titles you mentioned are considered "shojo"... just because a title centers around a romantic story doesn't necessarily make it a shojo title.
One of the classic "shonen" romances is in fact the title you mention as getting you into the genre, Video Girl Ai... and Oh My Goddess is another great example. Another which you didn't mention is Kimagure Orange Road...
The strict definition of whether or not a title is shonen/shojo is really which "phonebook" publication the title originally appeared in... for example, Video Girl Ai appeared in Shonen Jump which also features stuff like Dragonball Z, so it's considered shonen. Fushigi Yuugi originally appeared in Flower Comics IIRC, which is a shojo compilation.
Generally speaking, you can tell if a romance is shonen/shojo based on the central character in the story... as major a character as Ai is, Video Girl Ai really centers around Youta, just as Oh My Goddess centers around Keiichi. Fushigi Yuugi's story centers around Miaka, and the main character of Utena is obvious. But this may not necessarily be true all the time...
The lines between shonen and shojo, especially in the romance genre, are pretty blurred... and, as you've said, just because a title is considered shojo doesn't mean its readership is exclusively female. I consider Video Girl Ai as my favorite title, but a close second for me is "Koko wa Greenwood"... and that's a real weird title, as it's from a shojo publication originally yet features a predominantly male cast.
Hope this answers some questions... I know I thought for a long time that VGAi was a shojo title, until someone brought up these issues. VGAi certainly has more than its fair share of female fans, and the author (Masakazu Katsura) is considered among fans and peers alike as a master of romantic storytelling... check out I"s as an example of his romance work with virtually no sci-fi elements.