I only count about 35 votes in my votes tab.
The description says that I voted my max of 40 votes.
How is that possible?
Does this include deleted posts that I do not know about? And if that is true, do I have extra votes left for today?
I'd guess this was a caching issue on your profile page, as not long after you'd posted Bill the Lizard posted the comment:
I have you at 42 votes for the day in your votes summary (I can't see your votes tab, naturally). This does include deleted posts that you voted on, which also explains how you're able to vote more than 40 times in a day
Several times when I've voted on a lot of posts I've started receiving the five votes left message when my profile only shows around twenty votes for the day. I'm not sure exactly what the caching rules are but sometimes I've observed delays of around thirty minutes before the profile vote count is updated. Also note that the rules for getting the badge is based on UTC days, although that is also the way your votes for the day is calculated under your profile page.
So it means you reached 40 votes, the badge has been awarded, and then 5 posts you voted on have been deleted before you viewed your votes tab. You got to keep the badge, since it's not taken away after being awarded.