Pop3 servers allow access to messages by index ranging from 1 to n where there are n messages available. When messages are actually deleted (the deletes may be pending) the remaining messages will be reindexed.

Options are: remember how many messages remain on the server after deletions and start at the index following that number, read the message headers only and check the message id's to determine if the messages are new or not (assuming you keep the id's for messages that have been dealt with) or (as you suggest) check the date and times of messages.