I just tried Global Search for a string in the body of a sent message and had a similar result, same with Classic Search (Ctrl+Shift+F). First, I opened Sync. & Storage settings for each account, and checked Sent in the Advanced window, even if 'Keep messages in all folders...' was checked. This is necessary for the Body rule to be available in Classic Search. Then, rebuilt the global database; it takes a few minutes even with just a few 1000 messages (follow progress in Activity Manager). Finally, a Body search worked with Classic Search and also with Global Search.

I followed your steps, including de-selecting and then re-selecting the Sent folder from within the Advanced menu of Sync and Storage. I then rebuilt the database again. I'm seeing search results for other random text in the body of Sent messages now, which is progress, but my example case is still not working. For clarity, I'm searching a product key. It would have been copy/pasted to get it into the email in the first place, so is there a chance some kind of formatting is restricting the search results? I attempted to remove this as even a possible variable by copying directly from the sent message I wanted to appear in the search results. I wouldn't expect formatting(ie boldness/font) to be a factor in search at all anyway, but haven't verified whether that assumption is correct.

First, does the Classic Search find the message when applied to the Sent folder? Or, the Quick Filter Bar (Ctrl+Shift+K)? Also, I think Global Search doesn't index quoted text. GS should usually be a last resort after Classic or Quick Filter.

Neither classic search set to Sent nor quick filter while withing Sent find the message.