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.