The myaddress+shop@gmail.com should be trivial to defeat by a spammer. Its a very simple string remove/replace to get back to a stock email address, or change it to impersonate another service, eg. myaddress+netflix@gmail.com.
It's only useful for the actual service, after that, you can't rely on it.
The use of a "+" convention is just a convention popularized by Gmail and the other major providers. If you have your own domain, you should be able to do this with any arbitrary text schema, and encode some information in the address itself, especially if you don't care about sending email from those aliases: set up your email service to have a catchall inbox that can further be filtered/forwarded based on other rules.
It can be cumbersome but I could see it working at getting the information you're looking for.
Yeah, I love my catch-all email domain. If I start getting spam addressed to “Target@{my domain}” then I know Target sold my data; I can burn the account by auto-spamming everything addressed to it, and move on.