Hello,
I wonder if the problem is in your rule set somewhere. I have VPN tunnels configured to my workplace where I have access to both Windows Remote Desktop and VNC based hosts. Appart from my VPN rules for each of my required VPN subnets (Firewall: Rules @ LAN - Protocals = All, Source = LAN Subnet, Port = All, Desination = VPN Subnet, Port = All, Gateway = Default (*) <– NOT a balancer gateway here), I don't have any VNC rules set via policy based routing, and I have a dual WAN configuration. In fact, I don't have any VNC specific rules for inbound VNC or outbound VNC. I should add that I don't access VNC hosts which aren't being encrypted in some way - either by SSH or VPN, so I can't really test if outbound VNC is working to clients on the internet somewhere. I suspect that policy based routing might be required for this on a per port basis.
Speaking of ports, I remember playing with the ports within the server/client to get things working, but I attributed that to the fact that I have local VNC hosts running on my home LAN. Maybe you do too.
In order to get it to work, you could try changing the "display number" within VNC on any of the hosts you can control.
Display # 0 = 5900 (default)
Display # 1 = 5901
Display # 2 = 5902
etc..
You may want to try to specify the actual port within the VNC client (eg. 192.168.1.125:5904 vs. 192.168.1.125:4) to get things working. (I needed to for some clients, but not for all)
Give these suggestions a shot. Like I said above, I don't have any rules configured for inbound VNC as I tunnel in via SSH for LAN side connections... this way I get VPN like encryption when on the road without having to get my local host (hotels etc.) to open ports on their firewalls. Try turning off all VNC related rules to see if it makes a difference.
Sorry if this is as clear as mud, suffering through a bit of insomnia these days, and its the middle of the night here... I'm off to try to find sleep again.
Good night and good luck.
-- Phob