Another solution if you want to search domains and subdomains is have a column where the order of components of the domain are reversed, e.g. com.example.bar.foo.
If you use a wild card at the beginning of your search term no index can be used. On the other hand MyISAM supports FULLTEXT indexes. They may be what you need.
No worries I’ve moved this thread to the MySQL forum.
As for your question, I’d say first of all you need to add an index to that VARCHAR column. Unless you also get a lot of inserts and updates on the table, in which case the index might hurt you more than it helps.
As for InnoDB vs MyISAM, if memory serves MyISAM is faster at table scans and index scans than InnoDB, so you should probably go for MyISAM, but I’m not 100% sure.