Ace Hardware accepts a plus in the email, but then wasn't sending me a confirmation for my pickup order. When I contacted support, I was told my email on file was FOO%2Bace@gmail.com.
I bought my own domain and use whatever-service@mydomain.com to avoid exactly this problem.
Do you have all the mailboxes merge into 1, like a rewrite to email+alias? Or do you connect to a new mailbox per service?
I have them all merge into 1, but my mail software can still filter / whatever else based on the To field. Also if someone sells my email address I can just prevent that one from merging and send it into a black hole.