Depending on the size of @MESSAGE_IDS: if it's a relatively low number, you could always do something like:

my $sth=$dbh->prepare("DELETE FROM table WHERE ".
          join(" or ",map { "message_id = $_" } @MESSAGE_IDS));
[download]

If @MESSAGE_IDS is really large, consider breaking it up into smaller arrays when doing the above on each slice. Something like:

while (@MESSAGE_IDS) {
    my @todel=splice @MESSAGE_IDS,0,10;
    my $sth=$dbh->prepare("DELETE FROM table WHERE ".
          join(" or ",map { "message_id = $_" } @todel));
    $sth->execute;
}
[download]

Update: Or listen to lhoward :) He's got the best answer, I think. I also didn't realize you could do what beatnik suggested. I guess my SQL is off.