As far as I am aware I cannot used threads:shared since a hash of hashes is too complex.

Not so. Shared structures can be as complex as you like. You just have to learn a few relatively simple rules for setting them up and using them. By way of example, this do-nothing code demonstrates using a shared nested hash structure similar to that you describe.

#! perl -slw
use strict;
use Data::Dump qw[ pp ];
use threads;
use threads::shared;

my %hash :shared;
$hash{ serviceA } = &share( {} ); ## & necessary here!
$hash{ serviceB } = &share( {} );

$hash{ serviceA }{ "messageType$_" } = 0 for 0 .. 9;
$hash{ serviceB }{ "messageType$_" } = 0 for 0 .. 9;


sub thread {
    while( 1 ) {
        select '','','', 0.01; ## Simulate doing other things
        my $service = 'service' . ( qw[A B] )[ rand( 2 ) ];
        my $messageType = 'messageType' . int( rand 10 );
        lock %{ $hash{ $service } };
        ++$hash{ $service }{ $messageType };
    }
}

threads->new( \&thread )->detach for 1 .. 4;

while( 1 ) {
    sleep 1;
    lock %hash;
    pp \%hash;
}

__END__
[ 9:16:58.77] c:\test>junk2
{
  # tied threads::shared::tie
  serviceA => {
                # tied threads::shared::tie
                messageType0 => 15,
                messageType1 => 19,
                messageType2 => 23,
                messageType3 => 26,
                messageType4 => 16,
                messageType5 => 16,
                messageType6 => 18,
                messageType7 => 24,
                messageType8 => 17,
                messageType9 => 15,
              },
  serviceB => {
                # tied threads::shared::tie
                messageType0 => 19,
                messageType1 => 15,
                messageType2 => 20,
                messageType3 => 25,
                messageType4 => 22,
                messageType5 => 30,
                messageType6 => 25,
                messageType7 => 16,
                messageType8 => 16,
                messageType9 => 24,
              },
}

{
  # tied threads::shared::tie
  serviceA => {
                # tied threads::shared::tie
                messageType0 => 27,
                messageType1 => 37,
                messageType2 => 44,
                messageType3 => 48,
                messageType4 => 34,
                messageType5 => 44,
                messageType6 => 33,
                messageType7 => 48,
                messageType8 => 32,
                messageType9 => 45,
              },
  serviceB => {
                # tied threads::shared::tie
                messageType0 => 43,
                messageType1 => 32,
                messageType2 => 38,
                messageType3 => 47,
                messageType4 => 47,
                messageType5 => 60,
                messageType6 => 36,
                messageType7 => 41,
                messageType8 => 38,
                messageType9 => 38,
              },
}
[download]

Run the code above and note that four threads are incrementing randomly chosen counters, whilst the main thread is displaying them. Note the use of lock. Note that you cannot lock an individual key/value pair within a shared hash, you have to lock the entire (sub) hash.

I thought I could use the old Threads model

The old threading model is dead, (and has been for some time). Thread is now just a bad alias for threads.