If you’re using MyISAM, you can use full text indexing. See this tutorial
If you’re using a different storage engine, you could use a third party full text engine like sphinx, which can act as a storage engine for mysql or a separate server that can be queried.
With MySQL full text indexing a search on
A J Kelly would match
AJ Kelly (no to confuse matters but A, J and AJ would be ignored as they are too short by default and it would match on Kelly.) Generally Fulltext is much more forgiving (and usually faster than LIKE ’%string%’) because allows partial matches which can then be ranked on relevance.
You can also use SOUNDEX to make searches more forgiving by indexing the phonetic equivalents of words and search them by applying SOUNDEX on your search terms and then using those to search the index. With soundex
marry will all match, for example.
Having to use MyISAM tables is a bitter pill just for full-text indexing – you give up a lot of peace of mind, and things like Foreign Key constraints.
You could create a new column and make it the searchable version of the name by removing the whitespace, then set the column datatype as FULLTEXT (will only work with MyISAM). You may want to look into Lucene/SOLR as well. SOLR provides a number of tokenizers which work very well in this type of situation. Learning curve is fairly high, but worth it in the long run.