Do you have info on related sites (e.g. site X and Y are direct competitors?) If you do, you can use that for word clustering and find classes of related words. For example, if you have a set of 250 email providers, you might see "mail" and "email" a lot more than for domains in other categories, but you might also see something more subtle, like "postman" or "contact" or etc. Probably not as subtle (and cool) as Cyrus, but at least heading in the right direction.

Another idea: get a dump of Wikipedia and do a TF-IDF analysis on all of the words. When someone types "mail", you look at wikipedia.org/Mail and look for the most unique words. As it happens, the Mail article does mention Cyrus the Great, so as long as Cyrus is a pretty rare word in the corpus, it might be a suggestion you can make.

That said, there is such a thing as too clever. If I typed in "mail" as a domain search query you told me to create the website "CyrusMail", I would wonder what the heck that was all about because I don't happen to know the relationship between mail and Cyrus the Great.

For finding generically related words, maybe the wordnik API? http://www.wordnik.com/words/mail#related

More abstract relationships (mail -> Cyrus, image -> Lenna) might be gleaned by crawling Wikipedia.