I created a new temporary database and moved some of the mailboxes over and that fixed the problem for those mailboxes. So over the weekend I moved all the rest and then moved them back before deleting the temporary database.
Thanks AndyDavid for the suggestion!
Moving the mailbox must force a rebuild of the index. One of the major changes in Exchange 2019 from 2016 is that the index is now inside the database and is maintained by Bing technology known as BigFunnel. The vast majority of blog posts and tech forums posts about how to re-index an Exchange database are for 2016 and earlier. In most cases a fix from Exchange 2016 will work on 2019 but not in this case!
To find out which mailboxes have unindexed items, and how many, you can run this from the Exchange Management Shell...
Get-Mailbox -ResultSize Unlimited | Get-MailboxStatistics | ? {$_.BigfunnelNotIndexedCount -ge "1"} | ft DisplayName,BigfunnelNotIndexedCount
Obviously the "Microsoft Exchange Search Host Controller Service" and the "Microsoft Exchange Search" must be running and set to Automatic as they maintain the index.