How is that possible? I know that IANA has most of the .coms restricted, but other TLDs are available and I'm sure more are to come.
If you already use a registrar that supports your given TLD, have you tried contacting sales(or support) directly. Obviously the domains are valid, so it might just be dumb assumptions on their web site's front-end that they can work around by working with the registration process directly. It seems reasonable that they'd prefer doing that extra bit of work than to lose your business.
Moniker doesn't complain about searches for single-char domain names. (versus GoDaddy just plain saying they're "invalid.") Their search results page uses some icons that make it a bit confusing whether or not something's available, but I just tried a search for a domain that did turn out to be free, and it's offering to let me purchase, so it does work. You'll just have to get used to the interface.
There's a potential further complication in that you didn't say which actual TLD you were after, but they have a pretty wide selection available.
For whatever it's worth, o.co has MarkMonitor listed as the registrar, but they presumably offer that as part of their services, and not something you can just handle on your own.
Each registry choose what names are available or not. Things can also change: for example in
.FR 1 and 2 characters domain names were not available before and became available a few years ago.
As for gTLDs, they also have to follow ICANN rules, specifically on 2 letters domain names, as they are trying to resolve some possible confusability concerns (be they true or not is another matter).
Then, you may have specific eligibility requirements for these kinds of domain names, that prevent fully automated registration, which may make some registrars handling them and others not.
As for "unicode" domain names (called IDN in fact), this is another whole lot of problems by themselves, and this will vary a lot from one TLD to another (.COM being one of the more "open" to various characters, again it is debatable if this is a good idea or not).
In short, no generic rules, things change a lot from one TLD to another, and the time, as things change. Your best contact would be your trusted registrar of choice that should be able to clearly explain the situation to you based on which domain name you are trying to register.