Necessity is the mother of Innovation
With our back against the wall with limited budget and time we set about looking at innovative ways to address the issue. We drew upon experience of team members when matching credit card transactions of > 200MM per month. Choosing a cascading matching going from most conservative to loose matching allowed us to reduce the iteration run time from 3 days to 30 minutes and experiment to get the most optimal results.
Did I mention that we got enough time to try out multiple name matching algorithms (about five).