Here is a copy of the answer I got from mp3search.ru in regards to legitimacy:
MP3Search.ru is registered in Russia and has the license agreement
01-17 with Russian Organization for Multimedia and Digital Systems (ROMS,
www.roms.ru).
According to this Agreement we pay copyright royalties.
ROMS is the Russian organization on collective management of copyrights.
ROMS is authorized by the Russian Federation Law on copyright and related
rights to issue user licenses on behalf of all Russian and foreign copyright
holders.
We ask our customers to make a pre-payment before downloading and we do
not charge customer's card every time customer downloads a track because the
expenses involved in the transaction are much more than the price of a
single track. Otherwise we would have to fix higher prices, such as by iTunes
or MSN Music (about 0.99 USD).
There is no monthly payment, all your payments will be on your account
till you spend them.
You are welcome to join us!
Does this help!!!