SCP to deny tag deletion not working for SQS

One of the interesting things "under the hood" is that there isn't much that is centralised within AWS. One of those things is the evaluation of IAM (and by extension SCP) policies. So what works with one service doesn't necessarily work with another. This is a good example of that.

My general advice here (around SCPs) is not to use preventative controls when detective controls will do. It's very easy to get into a space where SCPs are very large (and bumping into size limits) with many exceptions (for all the things that exceptions are required for). SCPs are great for "this must never happen" type events. Things that are business critical events.

For everything else, consider using detective controls (usually in the form of Config Rules) because those give a lot more flexibility in terms of what you're looking for; and also many more ways to mitigate the problem afterwards (which could be alerting or automatically deployed fixes).

In these discussions I point customers at Eric Brandwine's excellent re:Invent talk where he walks through how the AWS security team has been on a very similar journey. Specifically that preventative controls are good for things that are super critical; and for things that aren't: detective controls are better. Because (in general) this path means that "security" doesn't get in the way of the business.