EWS do not have any similar feature as Recent flag in IMAP. Additionally, I think that this feature is not the best for you as I read your second paragraph. Only first session get Recent flag in IMAP that connects to the mailbox. So, if anybody other than your app connects to the mailbox, he/she gets the Recent flag of new messages and your app do not.
Better approach in my opinion is to use date and time of last check request and get all messages from that time. Then I would remember all item's IDs for future checks, last set of IDs should be enough. Using this you should get all messages.
This is the line to retrieve all messages since last check time:
ews.Search(EwsFolderId.Inbox, EwsSearchParameter.Arrived(lastCheckTime, null));
You can swap DateTime.Now and null parameter if you want.