Seems to be very consistent.
The easiest way was watching users as their posts were deleted and held for moderation. :P However, a more consistent way is to hold a user's post for moderation, and see if their post count goes down (it won't).
This is also true for when threads are deleted. As many users will attest to, the Folders' Lounge is deleted at the moment. I had 4k posts in that thread, and they should not still be counted in my profile.
Deleted posts (and posts within deleted thread) to not count towards a user's post count.
This also applies for posts held for moderation in my view, but I can accept that since it would automatically be removed if the post is indeed deleted, it's only purpose would be during the time it takes for a moderator to take action upon it, so we could get away with not doing it then... but since it's not on the public forum, I still think it shouldn't be counted.
It makes no sense for a user's profile to say they have most posts than they actually do. A deleted post should not being counted towards my total post count.
Take this user for example:
His profile says he has 26 posts, yet by checking his posts, you can only find 6. That's because his first 20 were deleted.