Had the same issue and just resolved.
Firstly and pleasingly - it is nothing to do with ARD. Think you will also find Traceroute is not behaiving correctly to offending machines. It is to do with network hiding addresses. ie if you jump onto to an affected machine and got o whatismyip.com - will bet it lists a hiding address ie - it is being nat'd. If you traceroute to the machine for the ARD mac you are using, you will probably find it resolves to the external address. It is to do with the way certain firewalls handle traffic routing of VPN Tunnels and at what point they are injected into the network.
Solution is to add a firewall rule (from your admin ARD mac IP or range) to reflect the actual IP (non Nat'd IP) of the machine. This will solve your problem. If I now trace to the offending mac servers, I get a fully resolved trace. Assuming you are connecting with a NAT Transversal gateway-gateway tunnel - this will work. It should also work for client to firewall access although I have not tested this.
Have over a 100 macs on one site and 20 were exhibiting this issue. By tracerouting and ascertaining what the differences where, came upon this as the solution. Made the change on the CheckPoing box, re-linked the IPSec tunnel and problem vanished!
2 years late but you never know as it might help someone....