Query performance Call Center data

Dear Experts,
I have a table related to call center call data with around 400 million rows and growing. It has data like phone number, IVR menu codes, call start, call end time and a unique call id for each call.
There is another process in the application which executes a query that performs count of the calls by phone number for different periods(Month, Quarter and Year) end date is current date.
And the most bad part of the query is the filter on phone number using a leading wild card. I explained the performance issues of this, but they don't want to change it, as that is how the parameter values are being searched from the application they said.
The table has necessary indexes.
CPU is always between 80 to 90% when this query runs.
I am thinking of implementing a staging table which would hold the call counts for the required periods for every phone number and then the application can query the staging table by just passing the phone number.
I would really appreciate your advice on this or any other method which can help improve the process.

Thank you