Thank you Phoenix, that's about what I expected after wasting a considerable amount of time searching for a solution. In case anyone feels adventurous enough to try their hand at using the above mentioned Perl modules, 2 things: first, good luck

and post your results if you figure it out! Secondly, I tried on two systems (Ubuntu 9.10 + Perl 5.10.0 and Redhat 5.4 + Perl 5.8.8) to use these modules without any luck. After getting past the actual install of this module and its dependencies (the ultra-reliable 'perl -MCPAN -e 'install module' failed on both systems so I had to manually download and install), the test code I prepared didn't return any errors, but it also couldn't trace any message despite using almost every conceivable combination of search terms.
I apologize if this is a little off topic for a Zimbra forum, but I feel like zmmsgtrace was a great weapon for any email admin's arsenal and a large portion of the Zimbra community would rejoice if an alternative could be found. Just my 2¢.