GMail has supported the "+" alias since the service was announced, one would think there'd be no excuse to not support it everywhere at this point. My consipiracy-theory hypothesis is that many companies "know" that any address with a + in it is an alias and actively filter it out. Because they don't want an alias, they want your _real_ address.
I run my own mail server and use a "." as the alias character. Haven't seen a system reject a single one of these.