I'd always used my own domain so I could switch providers without hassle, but then... I transitioned my gender, and changed my primary domain as part of that.

The thing that worked for me was making a big spreadsheet, working through it, and adding a label to messages still going to my old domain to catch stragglers.

Hopefully the last time I'll ever have to do this.