I'm sure you know about the little mail icon on the top bar. If you click on that, it will bring up your inbox, which you can switch to your sent messages.
You are correct that there is no search and that the messages are not linked to your match. Adding both of those would be excellent suggestions to make to MyHeritage.
With hundreds or more of messages, I can see you can have a big problem.
There are a few actions you can take that would hopefully help you a bit.
Whenever you contact someone, always ask them NOT to message you back via MyHeritage, but to send you an email. That way, your communication with them from that point on will go into your email storage. Most email systems (I use Outlook) are sortable by date or person and are easy to search.
At MyHeritage, in your Inbox settings, you should check the box for the option to send email alerts about new messages received to your inbox. Then you will have a record of receiving each message.
You could then also email yourself with the contents of the message they sent, so that you have it with your email. You can also email yourself with the contents of the message you send to others. Create a separate email folder for MyHeritage if you have as many messages as you say you do.
Personally, I use email for all my contacts in a big genealogy email folder as I just described. But as an alternative, you could use the separate database of people you've contacted that you say you maintain. That would be an excellent thing to do. But then you say you don't copy the message details into your database. Why not? Doing so wouldn't fix MyHeritage's messaging system, but it sure would make your database more useful to you and allow you to quickly see the correspondence you've had with each of your matches, which is really the ultimate goal.
The reason why you shouldn't rely on MyHeritage's messages is because you want all your communication to be in one place. And maybe you also have AncestryDNA matches, or GEDmatch matches, or people you are contacting because of a connection in FamilySearch? That would be four different systems and no matter how good or bad the individual systems may be, they are still disconnected systems. So choose just one system that works best for you: email, your database, or some other method to track all your DNA and genealogical communication with your relatives and potential relatives.