With google, i can use firstname.lastname@example.org. The random part is usually the site name. This lets me know who uses what email and possibly to block. The only place i have seen the + sign barred is Quicken for Mac 2015 Beta 4. (Beta 3 allowed it.)
I also have my own domain. I use a subdomain, so email addresses are email@example.com. This works except when the site does not support subdomains, which is probably because somebody wrote his own non-rfc-compliant address validator. Sub-domain seem to be safe from brute force spam, as they send it to domains, not sub-domains.