If I see a post which is vandalism (like this one, only visible to 10k users -- consisting of random characters), what am I supposed to flag it as? (Concretely, I remember both "spam" and "rude or abusive" flags being rejected. Do I need to raise an "other" flag and spend time writing a reason?)
Since I declined the flag, I'll answer why -- "spam" takes the definition that the post is intended to drive traffic somewhere else and does not disclose the authors affiliation with the post. "Rude and abusive" is for something that is offensive. Both of these are flags that will lead to IP addresses being rate limited or blocked outright, and so they should be used appropriately. They can also lead to reputation loss.
On the other hand, for a post like that one you linked to, something along the lines of "Not an answer" or "Very low quality" is a suitable flag and one that I would have marked as "helpful." For something that is initially posted as vandalism, raising the NAA flag or the VLQ flag is good. If a user edits an answer and turns it into junk like that one, then a custom flag to alert us to post vandalism is a safe option because we'll go look at the post and figure out whether it needs to be rolled back, locked, etc..
Ultimately, although I declined your flag, I still deleted the answer. Which means even if you use the wrong flag, it brought it to our attention and the action needed was taken. So using the wrong flag isn't a big deal really and won't penalize you in any way, unless you end up having mountains of declined flags.
According to our general guidance on flags, "very low quality" is the most appropriate flag type to choose for this kind of post. It would also be valid to flag it as "not an answer" (for obvious reasons), or "rude or abusive" (under the theory that this is abuse of the system, though that's really a theory that came from the higher-ups at SE; I think the moderator team here tends to think of the "rude or abusive" flag as being meant for abuse of people).
If, for some reason, you were unable to cast any of those flags, then you could cast a flag for moderator attention (a.k.a. "other"), but in that case you would need to explain in the flag message that you couldn't use any of the appropriate standard flag reasons.