Thanks, I'll give Jaro-Winkler a try.

I've already a strategy in place to filter the number of rows through to the fuzzy match query, including pre-weeding out exact matches and matches that don't start with the same first letter as the match target. (In my experience here, we tend to at least get the first letter of the name right!) Those filters alone are enough to bring 2+ minute queries down to sub-second queries, which is good enough for me.

Now if I could just get my nickname-based matching working as fast, I'd be a truly happy camper. 🙂