Sora wa Takaku Kaze wa Utau from Fate/Zero (2nd cour) -- it's a powerful song, and I think I listened to this one all the way through in every episode. Definitely one of my all time favorites.
Taiyou - Denpa-Teki na Kanojo. (This OVA is pretty obscure, I think.) Another powerful song. No visuals for most of the ending (just text credits scrolling) -- although 神戸守 (Mamoru Kanbe) listed as the director (監督) jumped out at me! No Klimt this time, but funny that I'm talking about something he worked on again already. Maybe I should go track down his other works more systematically...
Kesenai Tsumi - FMA 2003 -- I have a lot of nostalgia for this song and listened to it way too much as a teenager after my friends started introducing me to anime. The version on animethemes is a bit different from what I remember visually but the song is the same.
Wareta Ringo - Shin Sekai Yori -- I was actually thinking about posting an animepic clipped from this the other day since it popped back into my mind...
Hibari - Lord El-Melloi II Sei no Jikenbo: Rail Zeppelin Grace Note (the Fate/Zero spin-off series) -- I like both the song and the visuals (with the seasons changing)
My Pace -- Bleach ED6; I didn't much care for the filler seasons of Bleach, but the synth from this ED and the dancing characters got stuck in my head for a while.
X Jigen e Youkoso - Space Dandy. This one is memorable to me both for the "Hey, Everett..."/「ねぇ、エヴェレット」bit specifically and the general subject of the song.
Zzz - Nichijou -- both the art and song are great. There's a couple versions, but I like this first one the best.