I get an error of Invalid regexp: "Regular expression too big" if I try to put several thousand patterns joined by OR's.
regexp-opt exists for creating efficient regexps from a set of strings.
I've no idea whether that's actually going to cope with your input, mind; but if it manages to do so then you'll get a far more efficient pattern out of it.
The ways in which first and last names will be mixed and matched is still going to bloat things though (and probably a lot), so other food for thought on that...
You could divide the matching into first-name and remainder. Have a pattern for only the possible first names, and for each first name have a pattern for the possible full names beginning with that specific first name. When you get a match for a word which is someone's first name, pull up the other associated regexp and check whether you're looking at one of those.
Each of those regexps would be relatively concise, I think -- although you'll have plenty of duplication between each of the secondary regexps.
You could also have just two regexps, and search for "all possible first names" followed by "all possible remainders", and if you get a match for that you can check to see whether the matched text is actually one of your known names.