Thanks for the feedback.  Do you have some examples of that issue you can share?  A couple of strings that are returning different results dependent on the order?  One workaround I can think of might be to modify the UDF to always submit the shorter string first and the longer string second to the XP.  If you can post a couple of examples I'll see what I can come up with.

You can also calculate a Levenshtein Edit Distance "score".  Basically you take the calculated Edit Distance and divide by the longer of the two strings (be sure to CAST one of the operands as a floating point type).  The result is a "score" that estimates how closely the two strings match.  You might then set a threshold of returning only strings that match with a score of 80% (0.80) or greater.

As a matter of fact, I just thought of something else - I've had issues using UDF's in an ORDER BY clause before.  Not sure if it's documented as an issue on the MS website, but I have encountered that very issue.  I'll look into that as well.

Thanks again!