Unfortunately, rsyslog is one of the syslog collectors that don't like the output of Sys::Syslog.
In the end, we've decided to abandon Sys::Syslog and write some custom code that implements as much of RFC5424 as we need. We hope for better success with that, partly because we'll have more control over the code, and partly because we'll be implementing the current RFC, rather than RFC3164, which is what Sys::Syslog implements, and which has been obsolete for six years.
To everyone on this thread: many thanks for your help and suggestions.
