[saalweachter]

  1.  Get word lists for many languages, as well as vulgar word lists.
  2.  Generate Markov models for each word list, to generate words and score how much they sound like a regular or vulgar word in each language.
  3.  Make a list of words that sound like they could be a word in many different languages, but are not words and do not sound like vulgar words.
  4.  Find which of these words aren't domain names yet.

[gabereiser]

This is a logical approach until you have to explain how you came up with the name “Themicals”. If you’re selling a SaaS product maybe things like “Onychodon” may be a good fit but would kill you in the elevator pitch.

Btw, both of those names were made with Markov as you described.