I'll consider this a variation on moving state elsewhere. Now you have to keep the deleted resource forever. Or keep track of which environments the version with the removal directive is deployed to, or risk having orphaned resources in different environments.
It's not that bad as long as you have a reasonable deployment process. If you can't rely on your production state being fairly up to date relative to the Terraform definition, then you've got bigger problems than dealing with TF statefulness.
If you know that TF changes are guaranteed to be deployed within X days of writing them (e.g., with something like Atlantis, or even a weekly deployment schedule), then you can put a date in the comment of when the tombstone was added, and clean it up either automatically after X days or occasionally in a semi-automated sweep.
I agree having production updated frequently is ideal, but sometimes we don't get to choose when things are deployed when working with external clients. I'm glad Terraform doesn't dictate the workflow, so that we can fix one thing at a time.
And that would be a huge improvement! Code has history. Code can be managed with sed and grep. Code can be generated by tools I write myself.
Adding a tombstone for deletion, or a formerly-known-as tag for renames, is only "state" in the way that reserved tag numbers in protocol buffers are "state". It is a little annoying to have to do, and it creates clutter that you eventually have to go back and clean up, but neither of those is a dealbreaker, and in the meantime it solves the second-biggest problem with Terraform, which is the inscrutability of what it actually thinks it's doing when it comes up with a plan you don't expect. (The biggest problem is how ridiculously inexpressive HCL is as a language.)