As is obvious I am located in the US but my customers are in the former Soviet Republics. So I am looking to register a domain localized for them.
For example most web hosting providers in the US will register karlsonswidgets.com
or karlsonswidgets.cc
or .tv
or .co
for me, however, most if not all will not register .com.ua
or .ru
Are there any providers that will do such registrations for me?
I would separate the hosting from the registration process. Much easier to repoint the nameservers to another hosting company vs. attempting to get a combination hosting + registrar.
Check the list of accredited .ru registrars and .ua registrars. there are different requirements to register - for example, .ua allows only trademark holders to register domains similar to the name of the trademark.
Wikipedia has some additional info on .ua and .ru TLDs that may be of interest.