Over to you 
PowerGlove!  

Two years later... (I 
still don't use any kind of notification tool, so I often miss mentions.) 

I agree with OP and others that it doesn't make much sense to bare-quote the message you're being notified about.
I mean, what's the concern here? That someone will click through the quote and end up on an error-page if the topic no longer exists, or on a close-to-the-deleted-message topic-page otherwise? Those outcomes are expected, I think, when you've just been told that the message was deleted. 

I think it's more valuable to have the topic ID, the message ID, and the timestamp, than to have none of those things out of a desire to prevent confusion (especially when that confusion barrier is its own source of frustration).
I guess, if theymos is adamant about this one, then like shahzadafzal suggested, the next best thing might be to include the post's title somewhere in the deletion notice.
(I'd happily work up some patch options for this, but this stuff isn't part of my test environment, so all I can really do is appeal to theymos in my capacity as a bereft-of-code schlump.) 
Edit: Trimmed things down a bit, and removed the example (it wasn't a good example anyway; it itself contained a few link-quotes that I could have used at the time to recover the topic ID and remind myself where I posted it and what the context was).