I see, probably what is happening is that they are expecting you to use the old SSH version 1 approach for launching the SFTP server on the remote side.

Just to test that this is the case, what happens if you run these commands...?

plink *remoteHost* -p *remotePort* -v sftp-server
plink *remoteHost* -p *remotePort* -v /usr/lib/sftp-server
[download]

Does anyone of them hangs (that means that the sftp-server is listening) instead of exiting with an error?

Once you find how to launch the remote sftp-server, tell Net::SFTP::Foreign to use the same command with the open2_cmd constructor option. For instance:

my $sftp = Net::SFTP::Foreign->new(open2_cmd => "plink $host -p $port 
+/usr/lib/sftp-server");
$sftp->error and die "SFTP connection failed: " . $sftp->error;
[download]

update: and BTW, I think the root of the problem is an incomplete chroot'ed configuration for sshd in the remote side. Probably, they have not configured sshd to use internal-sftp server for the SFTP subsystem. Ask them to check that the sshd_config file contains the following line:

Subsystem  sftp  internal-sftp
[download]

(a how-to: http://www.debian-administration.org/articles/590)