Why different datetimes freezes a query based on indexes?

I have a table with a billion records. It has these columns:

Id bigint,
MobileNumber varchar(100),
Date datetime,
Message nvarchar(400)

And it has non-clustered indexes on MobileNumber and Date fields.

I want to find what a MobileNumber has sent us in a specified period. Thus I run this query:

select Message
from ReceivedMessages
where [Date] > 'from-time'
and [Date] < 'to-time'
and MobileNumber = 'number-to-filter'

And this query works lightening-speed fast for past 2 years. But when I change the from-time part to a closer date, it freezes out and takes more than 2 minutes to complete. In other words, based on different inputs, it behaves differently, sometimes even hanging out and not returning for more than 10 minutes.

I expected a consistent behavior. What do I miss about indexing? What can cause this inconsistent performance?

Update: I changed names of columns and table, so I can't attach execution plan as a picture. But here's the issue. Thanks for guiding me.

when I change value of date parameter, SQL changes index seek from IX_MobileNumber to IX_Date. I never thought that SQL creates execution plan based on the value of parameters. How that could be?

We have had the similar issue when dealing with big (billions of records) tables. As Martin Smith suggested in comment - you would probably need to periodically rebuild statistic data on that table.
This worked for us:

UPDATE STATISTICS  WITH FULLSCAN

This solution is kind of brute-force and being too simple but still it may help.

StackExchange Database Administrators Q#141400, answer score: 2