From all of the keys of your hash, grep those that refer to arrays with length larger than 1, and then delete the corresponding hash slice (all done in one go below):

use strict;
use warnings;
use Data::Dumper;
my %hash = (
    'Message1' => [ '0X026003', '0X026004' ], 
    'Message2' => [ '0X026007' ], 
    'Message3' => [ '0X026007' ], 
    'Message4' => [ '0X026005', '0X026006' ] 
    );

delete @hash{ grep { @{$hash{$_}} > 1 } keys %hash };
print Dumper \%hash;
[download]