Customer lookup for a mobile network's support agents

Your company runs a mobile phone network with 8 million customers. Its 1,500 support agents look up a customer at the start of most calls and chats. Agents type whatever the customer gives them into one search box. That can be a phone number in any format, such as 07700 900123 or +44 7700 900123. It can also be an email address, an account number such as AC-00482137, or a name and a postcode.

Today the box runs a LIKE '%...%' match across 6 columns of the customers table, and a lookup takes 8 to 20 seconds. Lookups should take under 1 second. Agents make about 60,000 a day, up to 5 a second. A customer who joined or changed their number a minute ago must be found.

How does one search box find the right customer, and what do you store so it is fast?