One further thought...
You say when you "try to connect over the Internet"... exactly what IP address or host URL are you trying to connect to? Do you have a "fixed IP" address?
Or, like most of us home users, do you have a DHCP-assigned IP address from your cable system or DSL provider? This DCHP-assigned IP address has a "lease period" associated with it and will change periodically (at least theoretically it can change periodically) when the "lease is renewed" and your provider assigns a new IP address to your modem.
Unless you have a fixed IP address you cannot successfully connect to any given IP address and have it be successful (even potentially, assuming your firewall problems are resolved) indefinitely. The best you can hope for is temporary success, until the IP address is changed.
An excellent solution is to use something like
DynDNS Hosts, as an intermediate hostname/IP-address re-direct/relay system. You define a symbolic "host name" that's maintained on their server. And you install a client program (
DynDNS Updater) on the machine you want to set up as a "host server" for remote access, which every 10 minutes updates the DynDNS server's hostname/IP table with whatever that machine's current IP address is (as currently "leased" to it by the ISP).
Then, any remote client (be it RealVNC, trying to connect to the VNC Server running on your host machine, or Remote Desktop trying to connect to your host machine) uses the symbolic "host name" (e.g. davidscomputer.dyndns.org) in the connection dialog, rather than a hard fixed IP address. Since "davidscomputer.dyndns.org" is registered to DynDNS, the resolution takes place there and the current (up to the most recent 10 minutes) IP address used to relay the connection to your target machine.
In other words, you don't connect to a fixed IP address. You connect to "davidscomputer.dyndns.org". This really is the only way to get around the renewable and thus periodically changing "leased" DHCP-assigned IP addresses almost always used for home Internet connections.
As expected, I have DynDNS Updater installed on EVERY one of the machines I support remotely (including my own) and that does not have fixed IP addresses (i.e. ALL of them!!). Each of those machines corresponds to a unique "hostname" defined in my account at DynDNS.
And, every one of these "host machines" is running VNC Server, supporting remote access by me through VNC Viewer (i.e. "client") installed on any machine I care to be able to use to connect to any "server" host machine. There is a VNC Address Book at the VNC "client" machine as well, which makes selection and connection (through VNC Viewer) super-simple when there are a large number of target host/server machines that are frequently being connected to, as in my own personal situation.
So each host machine runs both (a) VNC Server, and (b) DynDNS Updater. On any of my VNC client machines my VNC Viewer (i.e. Address Book) connection dialogs for each of these target hosts names their "hostname" as defined in my DynDNS account. Thus connection from any "client" machine I happen to be sitting at to any "host" machine I want to connect to is 100% assured, symbolically via "hostname" (i.e. through DynDNS) rather than through absolute IP address which is not a known value at any given time.
NOTE: DynDNS Hosts is free for 1-2 hostnames. I pay for
DynDNS Pro, because for me it's worth the $20/year cost for up to 30 hostnames -> IP, which is what I need.
RealVNC Personal Edition (which provides 256-bit AES secure encryption, which in my opinion is MANDATORY, as well as desktop scaling for use with small monitors, Address Book, file transfer, chat, printing from remote host on client printer, etc.) is $30.