This is two closely related things: a possible bug with the favorites implementation, and suggestions for changes to the favorites feature.

When trying to remove this deleted question from my favorites by clicking the star, I get the following:

The message is ridiculous, and removing from favorites should still work. It's not a serious issue, since deleted questions don't appear in the favorites list, but it's still very odd behavior (especially the message that is displayed). It might also clog the SQL tubes.

Here's the suggestion:

In light of flagging and possibly undeleting questions, adding to favorites would also make (at least some) sense; so there's no reason to restrict the favorites link for deleted questions — it can only be done by 10k+ rep users anyway, and one could assume they know what they're doing (some of the time).

It would also probably make sense for one's own favorite deleted questions to be visible for 10k+ users, so it's clear what happened to them (instead of simply disappearing), and allowing users to explicitly remove them from the favorites list, flag them, or starting the undelete process — it's probably the interesting questions that end up being favorites, so if they get removed, there's an above average chance that something went wrong. Again, it only applies to 10k+ rep users that have been around for a while.