In my case, middle name/initial wasn't of any real value in and of itself.

First initials are often an issue.

One step I have not yet taken is splitting up names into individual words, so Guthridge-Henderson matches with either Guthridge or Henderson at a fuzzyish level of matching.

Likewise, matching on common nicknames (Dick vs. Richard, Bob vs. Rob vs. Robert) I haven't implemented yet.

Matching on the first initial of nicknames, however, I'd judge as a lost cause (D matching R).

Addresses take quite a lot of cleanup, and even then, they're hard to match. Sending them out to a good address cleanup service is probably the best bet, but failing that, we have to try ourselves.