I decided to let my P1 account from the beta expire, and wanted to remove my vanity domain from the account.
Fair enough, my public website was still using it. So I reset it to use the xyz.sharepoint.com domain, and tried again. The "Cannot remove domain" error disappeared, but the new one "Unable to remove domain" showed up now:
So, I updated both of them, tried again, but the error remained. I couldn’t find any reference to my vanity domain anywhere at all, but I read in the Office 365 community forums that it might still be associated with my Lync account. I found the final solution to fix it in the following thread:
http://community.office365.com/en-us/f/148/p/293/706.aspx (post by Mike_MSFT on 2011-May-12 4:42 PM).
Once I was done with all users, I was able to remove the domain successfully.