You’re not posting the actual IP addresses, so it’s hard to tell whether this is something simple or not.
It’s quite possible this problem is related to NAT punch-through, and your firewall/internet modem/access point/router. If so, you may wish to set up port forwarding, and making sure you use your external IP address as the server address. (This may also be done automatically by Steam in many cases, but compatibility is always a concern.)
So, is NotMyIP a private or public addres? Is MyIP a private or public address? If one of them is private, it’s very likely NAT related.