I've long since lost my work on this, but the reason that the half-plys have to be removed is because you need to stop short of playing that 50th move with each iteration, meaning that the "initiative" (for lack of a better term) needs to shift to the other side after 99 ply, or 49.5 moves, not 50. This is how you end up down in the ~5850-5880 range.
I have calculated the longest possible chess game
NO NO NO please tell me you have more to do than this..take out the trash, feed the dog, work, groceries,TV , SEX? I will tell you...The chess game ends when the king is captured ...of course.. 

There are more important things than that, I think.
OK painting my toes is my last suggestion but but thats my last idea !
NO NO NO please tell me you have more to do than this..take out the trash, feed the dog, work, groceries,TV , SEX? I will tell you...The chess game ends when the king is captured ...of course..
We're all already on a website dedicated to killing time playing an inconsequential game.
NO NO NO please tell me you have more to do than this..take out the trash, feed the dog, work, groceries,TV , SEX? I will tell you...The chess game ends when the king is captured ...of course..
We're all already on a website dedicated to killing time playing an inconsequential game.
OH ! OH! its cap locks ! OH! OH! I SAY AGAIN ! Do not blaspheme this noble game of Emporers , Kings and Pirates ! For they are not wasting time..Oh no Baby my d luv.. They are in deep contemplation of the mysteries of life ! 
There's something being overlooked...
If one side loses the right to castle on one side, that counts as a change in position. That adds an extra 4 times that we can do the 49.5 move shuffle.
So we have: 96 pawn moves, 30 pieces to be captured, and 4 loss of castling privledges = 130. Multiply by 49.5, and you get 6435. Then add 1 more for the drawing move, and you get 6436.
EDIT: Never mind. That only matters for the 3 move rule, not the 50. So it's 126 * 49.5 = 6237, then + 1 = 6238.
I've seen this calculated independantly four or five times now, including having done it once myself and it invariably comes in somewhere in the 5850-5950 range (with most calculations being closer to 5850). Check the blog I referenced above for a very in-depth explanation.
OK, I see where I went wrong now. I overlooked that a pawn taking a piece means that the pawn is advancing AND a piece is being taken. Just ignore my previous comment.
More:
http://blog.chess.com/kurtgodden/the-longest-possible-chess-game
http://www.chess.com/forum/view/off-topic/the-longest-possible-chess-game
http://www.tomshardware.com/forum/48906-13-longest-chess-game
http://ficsforum.110mb.com/ficsforum/viewtopic.php?f=14&t=8
http://www.chesschat.org/showthread.php?t=12548
And so on....
To the OP Deranged, your answer of 5900 is a little simplistic. But it's in the right ballpark.
MrEdCollins, 5949 is also in the ballpark, but whomever came up with it rightly did not post their analysis (probably because it was too simplistic as well).
Cobra91, your number of 5898 matches exactly mine in the comments to the below referenced blog post by kurtgodden, except that I gave the answer with an extra 49.5 moves (99 ply).
RetGuvvie98, you're funny!
CM ilmago, yes your calculations also match exactly mine in the below post.
(note that with three separate people coming to the same answer it is very likely correct).
TheGrobe you've quoted exactly the post I did!
DavidMertz1 I do not think that losing the right to castle resets the move count. Also, making a move other than en passant in a position where en passant is legal does not reset the move count. If you believe otherwise, can you post a link? This would change matters of course.
http://blog.chess.com/kurtgodden/the-longest-possible-chess-game
There was also a "The Longest Possible Chess Game Revisited" blog, also by kurtgodden that featured another user's analysis, as well as mine in the comments. I'm not sure why he deleted it.
She is so not right. I think that we (the community) have the right answer anyways. 5898, under certain assumptions.
OK, I did it again anyway (really quick, back of the napkin, and without reviewing anyone else's anlaysis):
- 99 ply can be played prior to each pawn moved or capture (assuming the 50 move rule is enforced as opposed to voluntary) followed by a single move that is either a pawn move or a capture (= 100 ply per iteration)
- 8 captures are required for the pawns to pass each other (meaning 8 pawn moves must simultaneously be captures)
- The 16 pawns can make 6 moves each including promotion = 96 pawn moves
- 22 peices can be captured (excluding the two kings and the eight that are captured during a pawn advance) = 22 captures
- (96+22)x100 = 11800 ply = 5900 moves
This is the simplistic version. The problem is that both sides must be performing the pawn moves and captures, so there will be handful of iterations in which only 99 ply can be played so that the "initiative" can be transferred between the players.
The key question is how many times this must happen:
- As a prerequisite for the pawns to pass each other, at least four pawn moves must have been made by each side = 1 99 ply iteration to transfer "initiative"
- In order for the pawns to pass each other, each side must make four captures with their pawns = 1 99 ply iteration to transfer "initiative"
- Assuming that the back ranks could have been vacated efficiently so that the pawns can promote within each sides respective turn with the "initiative", each side must then promote their pawns in turn = 1 99 ply iteration to transfer "initiative"
- Once the second side to promote their pawns has captured all of the opposing side's peices (except for the King), he must turn control over to the side with the King to then pick off all of his remaining peices = 1 99 ply iteration to transfer "initiative"
So 5900 - 2 full moves = 5898 moves.
Pretty sure I came to a different number last time, so perhaps you're right ozzie.
I think the first time I did this I started with 5850 moves (missing the fact that you can shuffle knights for 99 ply before your first pawn move or capture), and missing one of the initiative transfers giving me 5848.5 or something similar.
Actually, the longest possible chess game is 50*117 + 25 = 5875 moves long, because of the twenty-five move rule. When it's down to kings plus a queen or rook, only 25 moves can remain.
There is a 25 move rule? I never heard of that. So if I have a king and queen vs a king and rook, I have just 25 moves to capture the rook?
There doesn't seem to be any such "25-move rule". Maybe the original poster was thinking the 50-move rule was 50 ply (so 25 full moves), but the rule is 50 moves, not 50 ply. Or maybe they were confusing chess with checkers, which does seem to have a 25-move rule?