Nah. You were right before. It's not quite trivial but it's not that hard either. You have two fronts to attack it. Double metaphone, like you said before, and just load up a mirror of your DB index with metaphone versions. IMDb, for example, does this with actor names. And the other is just to run the search through aspell or ispell. If something is spelled wrong and is not found in the DB index, suggest correctly spelled terms that are known to be in the index.

update: hadn't read ahead when I wrote this to see that creamygoodness also suggested Aspell already. Wasn't trying to steal any ideas. :)