Just the job for an AI agent!
So what I did is this - I wrote the app in Django, because it's what I'm familiar with.
Then in the view for the search page, I picked apart the search terms. If they start with "01" it's an old phone number so look in that column, if they start with "03" it's a new phone number so look in that column, if they start with "07" it's a mobile, if it's a letter followed by two digits it's a site code, if it's numeric but doesn't have a 0 at the start it's an internal number, and if it doesn't match anything then see if it exists as a substring in the description column.
There we go. Very fast and natural searching that Does What You Mean (mostly).
No Artificial Intelligence.
All done with Organic Home-grown Brute Force and Ignorance.
Because that's sometimes just what you need.