You want to use the UniqueId (UID) for the messages. This is specifically why it was created.
You will want to keep track of the last UID requested, and then, to request all new messages you use the message set "[UID]:*", where [UID] is the actual UID value.
For example, lets say the last message feteched had a unique id of "123456". You would fetch
123456:*
Then, discard the first returned message.
UIDs are 'supposed' to be stable across sessions, and never change, and always increase in value. The catch to verify this, is to check the UIDValidity when you select the folder. If the UIDValidity number hasn't changed, then the UIDs should still be valid across sessions.
Here are the relevant parts from the RFC:
2.3.1.1. Unique Identifier (UID) Message Attribute
A 32-bit value assigned to each message, which when used with the
unique identifier validity value (see below) forms a 64-bit value
that MUST NOT refer to any other message in the mailbox or any
subsequent mailbox with the same name forever. Unique identifiers
are assigned in a strictly ascending fashion in the mailbox; as each
message is added to the mailbox it is assigned a higher UID than the
message(s) which were added previously. Unlike message sequence
numbers, unique identifiers are not necessarily contiguous.
The unique identifier of a message MUST NOT change during the
session, and SHOULD NOT change between sessions. Any change of
unique identifiers between sessions MUST be detectable using the
UIDVALIDITY mechanism discussed below. Persistent unique identifiers
are required for a client to resynchronize its state from a previous
session with the server (e.g., disconnected or offline access
clients); this is discussed further in [IMAP-DISC].
Note: The next unique identifier value is intended to
provide a means for a client to determine whether any
messages have been delivered to the mailbox since the
previous time it checked this value.
Here is the link with more info:
http://www.faqs.org/rfcs/rfc3501.html
What I would do, is also keep track of the InternalDate of the messages downloaded. This way, if you ever lose UID sync, you can at least iterate through the messages, and find the last one you downloaded, based upon the InternalDate of the message.