Q:

The Rollback link doesn't work on deleted posts

If you try to roll back a post (either a question or an answer) from the revision history using the "Rollback" link, you get the popup asking if you're sure you want to roll back -- clicking OK ends up taking no action. (For completeness, clicking Cancel also does nothing.)
You can in fact roll back a post by clicking "Edit" on the revision, then simply clicking Save on the Edit screen, but if the Rollback link is available from the revision history (no reason why it shouldn't be), then it should work as expected.
If anyone with 10k wants to test this out, here is one of my testing questions on Meta that you can play with, so you don't have to create your own.
The rollback silently fails after the javascript gets a 404, like this:

POST http://workplace.stackexchange.com/posts/1881/rollback/6ad74a20-4590-4c60-86c9-781f968a0340 404 (Not Found) jquery.min.js:4

A:

If you are unable to use the rollback functionality, the link should not appear - this is now the case.

