The votes count summary on your main profile page includes deleted posts. Going to your full votes list for your account does not list delete posts, nor include them in the count at the top.
For example, my summary says I've cast 1,861 votes (1,281 up and 580 down), but going to my voting page, it says I've cast 1,247 up and 353 down (totaling 1,600). So I can logically deduce that 261 of the posts I've voted on in the past have been deleted now.
This is most noticeable when viewing your delete votes (if you have the privilege to delete), which would show up empty if all the posts you've ever voted to delete did, in fact, get deleted.