VM Public IP Address - Outgoing traffic

I have a VM on Azure that has a Public IP address assigned to it. Actually both the Public IP Address and the Private one are assigned to a single NIC that is in turn assigned to the VM.

Now, I'm trying to initiate a telnet from inside the VM, towards an external host, that needs the traffic to originate from the specific Public IP Address I'm using (they have whitelisted this IP).

So far this doesn't appear to be working. The connection always fails with time-out.

Now, I have created the required rule for outbound traffic in the Network settings for the VM to allow the specific port.

What could be the cause here?