Everywhere I have looked I haven't had a definitive answer. Are russian music websites such as legalsounds, mp3fiesta etc. legal in the UK and/or the USA?
The websites that do not obey the copyright laws in the UK and USA would not be legal to purchase from in those countries, no. Most, if not all, of those sites disobey the copyright laws.
Do they pay any royalties? They pay their taxes in Russia and that gets them some state immunity.. the US cartel haven't had much success with the Russian courts so far.