Gerome, I have repeated the process to delete the partition but then instead of partitioning it with Windows I have used the MP3 Player Disk Tool to add the new partition. After deleting the partition and reconnecting the player open the Disk Tool and go to the Partition Encrypt tab. Move the slider all the way right then back all the way left and press the start button.
Before doing this my player read as 2,039,545,856 bytes after it read as 2,045,247,488 bytes an extra 5 MB so I would say the problem has to do with Windows inefficient partitioning method. Can you try it and let me know if this recovers your 4MB?
Thanks Gerome.