I'd have to guess that you can only hit MSMQ using COM. If the Perl CGI is hosted on a Win32 box, you will likely want to use Win32::OLE to talk to the MSMQ. If you can describe how you would do it in VB or ASP, I can probably help translate. HTH
Now, if you want to send a massage, they call me magic hands. ;)