The suggestion to use the archive part of free SM is a good one. If you want these messages in M365, you'll need to do some work...
From within SM, you can do an archive search with just an email address in the To or From field, and then copy the result to a folder in a SM mailbox, but I don't know at what message count this might max out. And then not sure what will happen to system resources if you "Copy to Mailbox" after getting a huge result. Just searched a user's folder for all mail to them from 2010, and it made it to 100% after counting over 350,000 messages. I did not click "Copy to Mailbox," however.
Anyway, since the archive files are in plaintext EML format, as stated, there appears to be several ways to manipulate these and get them migrated to M365 (or elsewhere). What I don't know is how to automate the process of extracting the EML files from the ZIP archive files, and then separating them by user.
This should not be too difficult to program. I'm not much of a programmer these days, but I believe it can be done. If the client is large enough, they just might have a budget for this.
BTW there is at least one flavor of Microsoft 365 that doesn't include email, and which comes at a lower price. One of these would be Apps for Business, and can be mixed on a tenant with other M365 flavors.