Turns out it wasn't the email I used on Myspace.
Also, is Myspace back? Somehow my profile and pictures are on there again, but I thought they removed personal profiles years ago?
Posteo.de recycles deleted email addresses/aliases in three months. Fastmail is also similar and recycles them within three months or so. Same goes for Mailbox.org. All these paid services are pathetic in this regard.
Runbox.com (which I don’t use) is the only paid email service that clearly states that it never ever recycles email addresses, just like Gmail and Yahoo Mail don’t do either.
I’d like to know about privacy focused paid email services that have a clear policy of not recycling addresses.
Of course, as a reminder: This means you have to keep your custom domain, or else someone can register it after it expires and make any emails they want on it. But if you have a domain personal to you that you've used as part of your email address, you should probably keep it forever anyways.