IIRC, EvilLyrics has no database, per se. It searches a bunch of well-known lyrics sites, and if it doesn't have any luck on those, I think it just Googles the title and artist and pulls up the first hit or something

You recall correctly, but you're out of date. Go read the web site, especially the karaoke section.

Matthew