I’ve recategorized dozens of topics and seen others do the same, and everything worked relatively seamlessly. I have seen this happen a couple times, both with and without recategorization, but barring a momentary glitch, what I suspect we may be seeing is the user deleting the post (perhaps realizing they are in the wrong category, or having answered the question) right around the same time that we are interacting with it. Or it may be delayed action of the spam filter, moderation action or some other race condition.
For reference, the topic deleted by author issue may be relevant.