A recent favorite group that I discovered (through my wife) is Mew, a very complex pop Danish band. Check out their website and you'll immediately notice by the insane navbar at the top, and the audio, that this group is really different.
Their 3rd album, Frengers (2003), was their first big hit album (check out the songs: 156, Am I Wry and Snow Brigade on YouTube) and their latest, "Mew. and the Glass-Handed Kites" is amazing. Check out the video of their single from this album, Special.