The flip side to that scheme is that it's relatively easy to guess what the 'add part' is and so if a malicious party has obtained a legitimate 'base part' it's trivial for them to automate trying alternative 'add parts' on the most lucrative targets to find a valid combination by brute force. The random user part is impractical to brute force (the scheme I use has ~ 44 bits of entropy) but requires you to have access to a mail server where you can add as many user parts as you like to an email domain without (significant) additional costs to oneself.
Although all the above is true, I don't regard it as a significant weakness in your scheme. I tend myself to regard the random email address as 'security by obscurity' and really use it for the purposes of 'traitor tracing'. It's having a unique, random password per site that gives me some comfort. As you say, broken implementations that don't follow RFC822 et seq are the pain point for your scheme, and they are, from experience, so common that it's a serious drawback.