Ferret reader Dysfunksional Monkey mentions that there is an alternative to the karaoke Nokia mentioned below, in the form of the Karaophun! program which gives karaoke type features on a range of phones.

Only problem is that the software doesn’t seem to be available as yet on the Web site. Promised soon. Update: available here (thx DM!).