Of course, you could always take the brute force approach. 🙂
Create a table with all valid SSNs and set up a left join to it.
By today's standards a table of all valid SSNs wouldn't be that big (< 1 billion records of 1 int field as clustered index). Of course it might take a few days to generate, based on how many rules you want to include, but once finished you never have to do it again!
Kind of like a rainbow table used for the power of good!
But first, stop storing the damned things in an unencrypted fashion. 😉