$messageA->move($new_folder); // Moves msg ID 1
$messageB->move($new_folder); // Try to move msg ID 2 and fails

Why:
At least in Gmail, for some reason I was unable to pinpoint yet, PHP-IMAP is using MID (message number/ID) instead of UID (Unique ID). So, when we move the msg ID 1 the second message becomes the 1, so it fails to move ID 2 because it does not exist anymore.

Question:
Am I missing some setup to get it using UID instead of MID?