I suspect it will be hard to have a single request that both completes partial names and spell-checks sensibly. A spell check usually starts with the assumption that words are complete.
You can match names on the basis of
- How they look
- How they sound
- How they're actually used.
The problem with 1) is that simple fuzzy matching (edit distance) is not perfect. It's a short distance from john to joan and a long distance from bob to robert
The problem with 2) is that while we have phonetic analyzers they use exact-code matching only (there's no degrees of fuzziness) and they can have many false positives and false negatives.
Option 3 is the best but relies on a lot of data. If you have a load of strong IDs e.g customer account numbers/email addresses etc and for each, a bunch of associated names (including noise like typos, misheard pronunciations, shortened names etc) then you can machine-learn a thesaurus like this:
This is a weighted graph that can tell you janes is statistically more strongly associated with james than jane (probably because the n is next to m on the keyboard).
Not everyone is lucky enough to have these piles of data though which is why firms like Basis Technology offer specialised solutions.
It's not an easy problem.