CFIMAP returns a query object.. so instead of trying to retrieve newest to oldest, get only the unread emails and loop backwards through the query to process in the order you want.
^ _ ^
(UNTESTED, I've never used CFIMAP, so this is just a guess.)
UPDATE: Okay, I don't know that it returns a query object. If it doesn't, you can easily create a query object by iterating the results, and then use that query object sorted by date descending to insert into your database.