Why not just glom all your ids into one DBI statement, so that it looks like:

delete * from table where (id=1 or id=2 or id=3)

Example, extremely untested code:

$query = "delete from table where id=(";

for(@MESSAGE_IDS){
# you may need a "chomp" in here
  $query.=$_." or id=";
}
#Delete "or" off the back
$query=substr($query,0,-7));
#close the query
$query.=")";

my $sth= $dbh->prepare($query);
$sth->execute;
[download]

I wouldn't use this for huge deletes, but it should serve your purposes. If the "id" column is indexed, this should be pretty damn fast.