Hmm, it is a CGI script running under mod_perl via Apache::Registry (which I did not know at the time). It runs fine from a standrd CGI directory. Because I'm not using a mod_perl handler in the code, I guess I can't call "$r->send_cgi_header($header);" Is this correct?

My understanding - and it may be incorrect - is that the CGI.pm $query->header should send the header (according to this doc anyway) I've tried setting PerlSendHeader On and Off, but to no avail

It does send the header, before header() even returns. Your code should be:

#!/usr/local/bin/perl
use CGI;
use CGI::Carp qw(fatalsToBrowser);
use strict;
my $query = new CGI;
my $cookie = $query->cookie(
    -name    => 'test',
    -value   => 'banana'
);

print $query->header(-type => "text/html", -cookie => $cookie );

print "Hello";
[download]

under mod_perl (and if not an NPH script), that's the same as:

#!/usr/local/bin/perl
use CGI;
use CGI::Carp qw(fatalsToBrowser);
use strict;
my $query = new CGI;
my $cookie = $query->cookie(
    -name    => 'test',
    -value   => 'banana'
);

$query->header(-type => "text/html", -cookie => $cookie );

print "Hello";
[download]

which DOES send the header. Look at the source of CGI.pm