I noted a question that had 9 undelete votes, yet it was still deleted, and it was deleted by 10 people. Logically one could expect that it requires 10 votes to undelete, but the question still remains as to why there were 10 in the first place.
The number of votes needed to delete a question is at least three, but can be up to ten, depending on the score of the question and the attached answers. In this case the question needed ten votes (the maximum) to be delete.
The same is then true for the number of undelete votes.
For those that want the details:
Popular questions require more deletion votes to be deleted, at a ratio of 20:1 - a question's popularity is defined as: question score + top-scored answer score. For example, a question with (question score 15 + top answer score 5 = 20) will require 4 deletion votes (3 base votes + 1 popularity vote).
The maximum number of delete votes needed will not exceed 10.
Note that the above rules apply only to questions; answers take 3 votes, regardless of score.