For example, I searched for "[physics]book" hoping to get back results like "physicsfolio.com", "physicsreport.com", etc. My result was actually "physicsbook.com" -- which isn't even available.
So, the idea sounds great especially if you could create some intelligent parsing scripts and pull some good synonyms (possibly using the wordnik.com api?) then I think it would be another useful tool while searching for domain names.
Check http://www.wordnik.com/thesaurus/book for a good example of some synonyms for "book" which I'd love to see integrated with rewordio.us
For what it's worth, my favorite domain name whois tool is domaintyper.com -- consider integrating some of the features from that service (or even just the site mechanics) and I think you'd have a pretty decent product on your hands!