I use Quintessential Player to listen to my music and I could without any problem type all t.A.T.u. song titles in cyrillic. It also looks cool to have them displayed that way (Especially when showing them to others and they have no clue what the songs are called!)
http://www.quinnware.com
It has to be the latest version (Build 50 or higher) the last official release (3.51) didn't have all the Unicode stuff done yet.
Just a funny thing though, at work I run WinME and even with the Russian Keyboard installed I couldn't type in any song titles in russian. So I had to do it here (WinXP) and bring them to the office.
Also another thing, I use Ogg files instead of MP3s in case that might matter.