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.

Since you have some common filtering between those queries, you might be able to speed things up, and reduce the amount of locking / blocking going on, by adding a filtered index on the "Active" and "Status" columns.

It's difficult to tell which columns belong to which tables without the schema, but the index would look something like this:

CREATE NONCLUSTERED INDEX IX_BatchID_Filtered
ON dbo.MessagesSent (BatchID, Active, Status)
WHERE Active = 'True' AND Status = 'Queued';

Note: there might be a better leading column than BatchID, and you might want to include other columns from the table (like DialString, System, QPriority, etc) - I just wasn't which columns belonged to which tables, and what their data types are, etc.

This index would only include the (hopefully small) subset of rows that meet those criteria, and provide more predictable performance in the face of somewhat out-of-date statistics.