I am not sure the fastest way to do this kind of search in sql server, maybe a regular expression?

Let's say I have a 6 character varchar field. In that field are license plate nunbers, such as "L1 234", "QA3333", etc. Now the user enters via a telephone 6 numbers. (I cannot control the IVR portion and must deal with the 6 numbers.) Now given the phone pad, if a user enters "235466" that could really mean:
235466
A35466
B35466
C35466
2A5466
2B5466

etc for millions of combinations. I need to pull the recordfs that match any of those possibilities.

Comments?