I guess that this is not a Perl problem. Here are some tests you should run:

Try adding explicit :80 or :443 to the URL.	Doesn't work? This really seems to be a Perl problem, contact LWP support/maintainer
Try start a local TCP server on port 4430 and connect to 127.0.0.1:4430 on the ISP server.	Doesn't work? Really strange, contact your ISP and ask for firewall or non-standard server configuration.
Use telnet 123.321.123.321 4430 on the ISP server and look if you get a connection (no automatic reply is expected).	Doesn't work? You clearly have a network issue with your ISP or did some blocking configuration on your server.
All above worked? Try another target server and/or port for testing. I'll /msg you the URL of a private machine of mine which runs a httpd on 8080.	Works? The server 123.321.123.321 doesn't like your ISP server. Get another ISP.
Still no hint? Get someone to start a webserver on port 4430 on his ISP server and try this.	Works: 123.321.123.321 doesn't like your ISP server. Doesn't work: You ISP doesn't like port 4430, get another port or ISP.

Notice:

All the hints are hints not this-must-be-the-reason-things.

There may be still some really stange OS, Perl, protocol or lib issues which would make it really really hard to find.

Yes, I noticed that 123.321.123.321 is not a valid IP. I just reused your placeholder for the hints. :-)