Which is covered by GP's second suggestion. I add short random password-like strings to these aliases to thwart spammers who might be trying obvious aliases, turning e.g paypal@example.com into paypal.nsi873g@example.com

I probably didn’t explain myself well.

On Gmail foo+bar@gmail.com is an “alias” for foo@gmail.com. So if you give someone foo+randomstring@gmail.com hoping that will help you map random string to that particular sender, you’re fucked - because anyone who sees foo+randomstring@gmail.com knows it’s an alias for foo@gmail.com, they can just email that directly and bypass your cleverness.

If you’re using a sane alias provider like you described, then it’s likely not an issue.