Looking at your code below:

    ...
    my $msg = $Folder->Items($i);
    my $attachments = $msg->attachments;
    if ($attachments->Count) {
    print "removing...";
    while ($attachments->Count) {
        $attachments->Remove(1);
    }
    ...
[download]

My gut feeling is that you are only modifying a local copy of the message, not from the actual outlook mail box. But I need to confirm this with some test later since I do not have access to Outlook at the moment.