About Gmail, we can probably easily implement something like this: https://www.onebigfluke.com/2013/06/bootstrapping-webfinger-with-webfist.html
And it wouldn't be disruptive to NIP-05 at all as we would hardcode just the top 5 big email providers (I don't even know if there are this many).