Normally I would suggest TeamViewer.com, but you are talking a commercial situation which should be paid for, and you mentioned financial issues.
I do not understand the VNC not working, as I've used Screen Sharing (just Apple wrapped VNC) both to and from Lion to other Macs.
Can you please describe the configuration information
What VNC clients? (Mac OS X Screen Sharing, Chicken (or Chicken of the VNC), JollysFastVNC, TightVNC, UltraVNC, RealVNC, other...)
What VNC server? (Screen Sharing, Remote Desktop, Vine Server, other...)
What computer is trying to connect to the remote offices? Is it a Mac or other
What operating system version (is this the Lion system?)
What is the office Mac? Is that the Lion system?
What do you have as a router at work?
Can you configure your work router to allow VNC ports 5900, 5901, 5902, ... through your router and vector the different port numbers to specific Office Macs? <http://portforward.com>
Have you tried Mac OS X Screen Sharing? On the Office Mac you enable System Preferences -> Sharing -> Screen Sharing (optionally, you can enable a VNC password for non-Mac clients). On the Mac client, you use Finder -> Go -> Connect to server -> vnc://address.of.office.router:5903 which would connect to port 5903 on the office router which you would have previously port forwarded to a specific office Mac.
If you are in the office, then you should see the Mac via bonjour in your Finder side-bar or via Finder -> Go -> Connector to server -> Browser
Anyway
No-IP.com or DynDNS.org can provide a dynamic DNS name to make finding your office router easier.