Re: Gmail?
Sub-addressing, sendmail calls it "plus addressing", it's been around since at least sendmail 8.36 (early 1993) this is far from a Googlism. The RFC821 spec for the "local part" to the left of the @ is surprisingly loose, and most systems will choke on one thing or another.
http://en.wikipedia.org/wiki/Email_address#Address_tags