You should prepare the statement once outside the loop and then bind and execute it inside the loop

my $sth = $dbh->prepare("DELETE * FROM table 
                                   WHERE message_id = ?");

while $i (@MESSAGE_IDS){
          $sth->bind($i)
          $sth->execute();
          # and so on ...
        }
[download]

Check the perldoc for DBI - this is off the top of my head.