My experience with IMAP has been that you can never count on two imap servers to handle things in the same way. The pod does offer this small piece of advice:

delete_message returns the number of messages it was told to delete. However, since the delete is done by issuing the +FLAGS.SILENT option of the STORE IMAP client command, there is no guarantee that the delete was successful for every message. In this manner the delete_message method sacrifices accuracy for speed. If you must have guaranteed results then use the IMAP STORE client command (via the default method) and use the +FLAGS (\Deleted) option, and then parse your results manually. Eg:

$imap->store($msg_id,'+FLAGS (\Deleted)');
my @results = $imap->History($imap->Transaction);
...                     # code to parse output goes here