You could use a service. Let's assume that any cost should be modest. DomainTools Domain Typo Finder might satisfy your requirements. Search options are as follows, selected individually or in any combination:
- Qwerty typos, for QWERTY keyboard slips
- Letter swap
- Sticky keys, for extra or missing letters
- Look a-likes e.g. the letter
l versus the number 1
There are three "viewpoints" for searching. Registrant is the default. DNS is described as
"a sortable view showing the name server and IP address of each typo"
TLD finds typos in names in any of these 6 Top Level Domains,.com .net .org .biz .us .info and indicates whether or not the domain is registered.
Is it any different than OP's discarded alternatives?
Maybe. It claims to "find common typo's associated with domain names". That means the data was collected from users as they manually typed domain names into their browser "navigation bar". I'd want to confirm the veracity of that conjecture with DomainTools.
Domain Typo Finder's "Sticky keys" search includes common variants, with or without hyphens. Those kind of typos aren't due to physically gummed-up, sticky keys; it is an error in human perception. That indicates use of something better than a rule based, expert-system approach, or worse yet, an alphanumeric string-checking, combinatorial RegEx horror...
How robust is the methodology?
I don't know. They might give details, or use a "best practice" form of NLP (Natural Language Processing) or semantic analysis which I failed to locate on their website.
Domain Typo Finder is free on a "limited basis" for human, unscripted use. DomainTools paid members are limited to "reasonable levels of human, unscripted use". API access may be available for paid members; OP's inquiry doesn't require API access though.
I was suspicious of a free service that utilized text analysis (even though structured, which is easier than unstructured) and machine learning to be effective i.e. seems too good to be true. Have no fear! There are costs to use Domain Typo Finder with all features, especially DNS and TLD views. The output from those searches seems to require either a one-time charge by report, depending on volume of results, or payment of the monthly DomainTools membership fee of $49.95.
Disclosure
I use DomainTools, always, when doing Whois look-up's for my Web Of Trust activities. WOT is a crowd-sourced browser add-on/ extension, based in Finland, in which I have no financial interest, no compensated affiliation, nor have I ever been a paying customer. The same is true regarding DomainTools. I have no financial interest, am not an affiliate, nor have I ever been a paying customer.