Sent Box Behaviors set to Never delete sent items since I started. There are roughly 12,000 emails in there ....
So - makes me wonder, what is the indexing capability of Mail and/or Spotlight? (I do not know the answer to that one.)
Spotlight does find email messages by title or content. Why not try looking for those replies using Spotlight to search on the message Subject? Just a thought.
Are you configured to keep messages locally for off-line viewing and saved on the server? Spotlight is only searching the local mailboxes. I do not know if Mail looks both in Server bases mailboxes and local. Something for you to test and learn.
Some of web based email servers have their own maintenance and deleted schedules. My Gmail tells me to set all the local settings to "never", etc. and then the Gmail servers delete and clean up on their own schedules ignoring the settings in Apple Mail.
I am sorry I don't have a better understanding of your specific situation, but if you can use other tools (Finder -> Find and Spotlight) to locate the message replies, that might put you on a path to figuring out why Apple Mail cannot locate the messages.
You can post a new thread: "What is the maximum number of local messages that Apple Mail can index properly?" To me, 12,000 seems like a lot; but then I wrote my first data bases on 1 MB external floppy drives so I may have a warped sense of limits for current systems. 😉