I'm not sure this is a *bug* rather than a feature, but I'm not sure it isn't either.
If you make a post with an attachment and embed that attachment into that post, then delete the attachment, to me it should clean up the embedding in that post.
I don't mean "attachment 1 is attached to post 2, and embedded in 2, 3 and 4 and if I delete attachment 1 it should house clean 2 and 3 and 4" because that's neither practical nor reasonable.
But if attachment 1 is attached to post 2 and embedded in posts 2, 3 and 4, if I delete the attachment the embedding from post 2 *should* be removed because we can know there if that's the case.
Perhaps even replace with a generic "(this attachment was removed)" rather than the current error message which is somewhat ambiguous in meaning.
We could try to automatically remove the attach BBC from the post, I suppose, but I think it would be cleaner to simply improve the error message like you suggest in the last part of your post. That will be more consistent and less error prone, since we won't need to distinguish between cases or run additional queries.
Definitely the message could do with some love - but I'd still like to see the attach bbc stripped if nothing else but to save the additional processing otherwise.
Fixed in 2.1.3.