[ This post is the a continuation of my previous work on the subject. ]

Solved!!

Right from the start, I was dismayed at the lack of documentation of PostData's type. (Saying Variant is totally meaningless.) After lots of research, I found how to format the data to IE's liking.

use strict;
use warnings;

use Win32::OLE             qw( );
use Win32::OLE::Variant; # qw( Variant VT_* );

my $IE = Win32::OLE->new("InternetExplorer.Application")
   or die("Could not start Internet Explorer.Application\n");
 
$IE->{visible} = 1;

my $url       = "http://amos.shop.com/amos/cc/main/ccn_search/ccsyn/15
+0/stid/6150608";
my $post_data = "search_form=&st=socks&sy=products&search_button.x=39&
+search_button.y=12";

$IE->Navigate(
   $url,
   undef,
   undef,
   Variant(VT_UI1, $post_data),
   "Content-Type: application/x-www-form-urlencoded\r\n",
);

# Alternative Syntax
# ==================
#
# $IE->Navigate($url, {
#    PostData => Variant(VT_UI1, $post_data),
#    Headers  => "Content-Type: application/x-www-form-urlencoded\r\n"
+,
# });
[download]

The CGI script I used for debugging returned:

REQUEST_METHOD=POST
CONTENT_LENGTH=71
CONTENT_TYPE=application/x-www-form-urlencoded

Content length: 71
Content (hex):  7365617263685f666f726d3d2673743d736f636b732673793d7072
+6f6475637473267365617263685f627574746f6e2e783d3339267365617263685f627
+574746f6e2e793d3132
Content:        search_form=&st=socks&sy=products&search_button.x=39&s
+earch_button.y=12
[download]