Welcome the the EMD forums, cygnusX88!
I'm just taking a guess here - but I would expect that messages are identified by a message-ID that doesn't change, not serial numbers that would change after every deletion. (POP3 has been used successfully for too long a long time for the protocol to be a problem
) Can you find a message-ID associated with each of the headers you downloaded?