Imap.GetMessageInfoByUID retrieves several IMAP parameters including flags.
Those parameters are as follows: RFC822.SIZE, INTERNALDATE, FLAGS, ENVELOPE, BODYSTRUCTURE and in case of Gmail: X-GM-THRID, X-GM-MSGID, X-GM-LABELS.
To diagnose this further, please turn on logging:
If the flags are not in the server response there is nothing you can do - you must use GetFlagsByUID(List uids). Make sure you are using the overload with uid list as argument. Retrieving data in bulk is generally much faster, then invoking this method for every uid.