Okay, this isn't an AMV yet, just an idea for one.
I was thinking of how Kings and Queens from Audio Adrenaline fit a lot of different anime characters very well. Link is http://www.youtube.com/watch?v=HA_U11B1Ss8
The characters I was thinking of are Naruto, Ed, possibly Tohru from FB, and Rat from No. 6. Listen to the song and you might see why.
So, if anyone's bored and good at that sort of thing, I would love to see this happen because there are so few good AMVs to Christian songs out there.