Well, its turns out to be quite easy in the end.

There is no required format for the Message Id, so it can be pretty much anything you like, but it does have to be unique. However, as has been noted, the general accepted format of a Message Id is $a(separator)$b@domain_name, where $a is essentially some form of timestamp and $b is some form of random element. So, here is what I created. The timestamp is generated from localtime and a random number from rand().

my @dayofweek = (qw(Sun Mon Tue Wed Thu Fri Sat));
my @monthnames = (qw(Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec))
+;
my ($sec,$min,$hour,$mday,$mon,$year,$wday,$yday, $isdst) = localtime(
+);
$year += 1900;
my $ran_num = int(rand(100000)); #This is a 5 figure random number whi
+ch ensures the MID is really, really unique!

# Create a Message Id
my $MID = sprintf("<%04d:%02d:%s:%s-%02d:%02d:%02d-%05d\@company_name.
+com>",
$year, $mday, $monthnames[$mon], $dayofweek[$wday], $hour, $min, $sec,
+ $ran_num);
[download]

And this is an example of what $MID looks like:

<2017:21:May:Sun-07:36:11-57049@company_name.com>

spamassassin seemed to think this was ok and so lowered the spam score accordingly, so helping prevent my script-generated emails ending up in the spam folder.

Many thanks to those who replied. I appreciated your comments and suggestions.

Geoffrey