VPS Provider that is not blocked in Russia?

This is a well known issue for Russians and many websites are affected by it. Selecting another host may only give you a temporary solution as Russia can update their blacklist at any time. If you really NEED to service Russian users you’ll have to host in Russia, but that will probably be a bureaucratic nightmare.