Nothing worse than an intermittent problem...
...so that the sender email address matched my domain. That worked. But now even when I change it back to a random address it works.
I would stick with using a real address (matching your domain). What is the purpose of a "random" address? The field is there for a reason. Perhaps the mail system doesn't blacklist you for a fake address immediately, but after seeing several over a short period, it concludes you're spamming or otherwise doing something nasty.
When I use the Track Delivery program in the control panel, sometimes it says it succeeded in sending the email with the attachment (but I don't receive it). Sometimes it gives the error "SMTP error from remote mail server after MAIL FROM:<firstname.lastname@example.org> SIZE=1733: 452 Space shortage, please try later"
"Space shortage" sounds like a different problem than domain mismatches or other security issues. The recipient's mail system is apparently saying that it ran out of space to store what you sent. Is this a huge PDF you're attaching? Can small emails get through to this recipient? Do they even allow
attachments, or restrict the type? Maybe this recipient is one of those problem people who leave all their emails on the mail system, rather than downloading it to their PC, and eventually run low on space. If so, it's your recipient's fault, not yours.
If it's a few recipients who have space problems, perhaps you should not be attaching (large) PDFs. You might want to consider just sending a link to the PDF (with some long, random key in the URL), and making the recipient pull in and download the PDF as a separate action. You may need to encrypt the PDF, if it contains sensitive information, and supply the key in another email.