iMessage (iOS 10) doesn't index messages properly
According to Apple's engineering department, backups only store the past 200 messages in the search database. The rest are stored for regular viewing, just not in the database.

"What the customer is experiencing is actually considered expected behavior.  With the release of iOS 10, customers are now only able to search the last 200 messages with Spotlight or the in-app search. This would include the last 200 sent and received messages.

The 200 searchable messages limit is only after restoring from a backup prior to iOS 10.  This is why devices that had the same Messages database and were not restored from a backup when they upgraded to iOS 10 can still search prior to the 200 limit.

If the customer would like to see this function in a different manner going forward, please encourage the customer to submit feedback at apple.com/feedback. “