Query execution plan is horrible until Statistics are Updated
You could use a manual plan guide to enforce the desired plan.  

Alternatively, you could use Query Store to enforce plan guides via the GUI.

Also, you could run an update statistics job after the big load of messages.  I wrote a post on my blog showing an easy way to do that.