I think when accented characters should be normalised when searching. Lots of English language users don't know offhand how to enter accented characters and lots of band and song names with accents are sometimes used without accents. For example the (cliché warning) heavy metal umlaut. Tracks by the band Leftöver Crack most often have Leftover Crack as the artist but some may have Leftöver Crack instead. So a user searching for either Leftover Crack or Leftöver Crack would get results with artist names both Leftöver Crack and Leftover Crack (just as they already get leFTOver cRACk). Also although I know little I think there are some unicode standards for normalisation. It'd probably be best to use one of them.

Other information: