The way I reckon it happens is that the database record for post count doesn't get updated when a post is deleted.
So it's showing 20 posts per page. Say a thread has 21 posts, so it's just on its second page. Someone yanks a post. There are only 20 posts (only one page's worth) but whatever mechanism that's responsible for pagination of the nav bars still thinks there are 21 posts because a post deletion doesn't update the post count record. So when that 20 post thread is displayed, the nav bar still shows a second page available.