Finally found the problem, RealVNC.
I had to install it for some reason a few months ago to get the viewer. Apparently it doesn't ask or anything if you want to also install the server, so it did. The (non-working) RealVNC server hence listened on all the ports instead of TightVNC or UltraVNC.
Disabled the RealVNC server service and fixed all my problems
You need a reverse SSH tunnel, and a regular SSH tunnel, and you join them together in the middle.
We have 3 machines. Friend, Server, Mac.
From Friend, you connect to Server using SSH, setting up a tunnel in the reverse direction.
ssh -R 9999:localhost:5900 user@Server
This creates an ssh session from Friend, to Server. On Server it listens on port 9999 (on the localhost address), and forwards anything on that port, back to Friend on port 5900 (through the ssh tunnel, so the firewall doesn't block it).
On Friend, you now need to ensure there's a VNC server listening on port 5900 (this is the default port for VNC servers).
Then, from Mac, you do this,
ssh -L 9999:localhost:9999 user@Server
That tunnels everything on port 9999 at your end, to port 9999 on the localhost on Server. Since 9999 on Server is then forwarded to Friend, you've joined the tunnels together.
Now, you can open a VNC Client on Mac, and connect it to port 9999 (i.e. when it asks what to connect to, you connect to 127.0.0.1:9999).
The ssh daemon on Server needs to support port forwarding for this to work.
You can do this with only one tunnel (the reverse tunnel from Friend using a slightly different format), but that leaves the Friend computer at risk because it would allow anyone to VNC to Friend by connecting to the port on Server's public IP address. This way, only you can connect.
Best Answer
If you are willing/able to use an alternative solution, I suggest teamviewer.
It's free for non commercial usage. Usage is really simple.
Other user can use given user/password combo to remotely connect and control the PC.