Does anyone know of a payment provider/gateway that deals with Russia ??

You should apply for merchant acc, and then ask at your bank with which gateway they do work.

Check out http://www.wmtransfer.com, it's the most popular electronic payment system in Russia now...

If you are from Russia, then check assist.ru or cyberplat.ru
If you are looking for a processor who can bill russian clients , then many processor should do that. Just ask them to open the country if they blocked it to prevent fraud (stupid way to fight against fraud)