I had to implement something similar not too long ago. Had to also do % matching as well. In my case though, I couldn't change the underlying database and I was lucky enough to be able to narrow results down to around 100 or so before having to calculate it. I ended up settling on a combination of Levenshtein and Double-Metaphone.

If you can add a column to the underlying table, then you might want to look at just calculating the double-metaphone and storing the hashes it creates in a couple columns. Then you can compare on the double-metaphone hashes in SQL vs. calculating on the fly.

Here's an article where a guy did it and stored the hash as a UDT.
http://www.sqlservercentral.com/articles/.Net/doublemetaphonephonecticmatching/2063/