Mac mail “remove attachments” moves message, but doesn’t remove attachments

Go ahead and delete that "recovered" folder, and there is also going to be an .OfflineCache folder that needs to be removed. Note the period at the beginning of the file name; you will either need to show invisible files or use Terminal to delete that folder.

This most often happens when an unsuitable large file is attached to a message. With GMail for example, any attachment over 20MB will be rejected. Mail sees the rejection by the mail server and tries to recover from it by sending the message again. Over time, these half-attempts to send mail stack up and start using all your drive space.

If you want a quick and easy way around the problem, remove the account in Mail's preferences, then re-add it. This will discard the offline cache for the account and free up your mangled space, at the expense of having to re-download the real messages.

And in the future, don't sent huge attachments. Use a specialized service like Dropbox instead.

The problem indeed was with synchronisation: my iMac had this account configured as name@company.com, while MBA had this account configure as name.alias@company.com. Once I have deleted all IMAP accounts from both iMac and MBA and created it once again, problem disappeared.