Idle hands and thought make for interesting ideas...

[Kalium]

Ideas. Plural for a reason. Have fun with these, I lack the artistic ability, skill, time, and programs. Not to mentions source.

I Will Remember You - Sarah McLaughlan - Tenchi in Tokyo (possible lip-sync) Similar in concept to the "Is This Love Video", I guess.
Brown Eyed Girl - Van Morrison - Angelic Layer (need I explain? there are two guys to work with)
One Tin Soldier - (horror of war concept. Gundam maybe? I was thinking maybe Scryed)
Princes of the Universe - Queen - (various anime heros/badasses. Self-explanatory if you know the song)
Somewhere Out There - Our Lady Peace - Crest of the Stars series (Crest just somehow lends itself to this)