Not knowing the specifics of the 'other' companys' networks, from what you say, it sounds as if the problem will be on their end. Several other companies are connecting through the PPTP VPN you have setup just fine, plus you are connecting just fine during your testing. For the company who is having issues, it's not that their policies are too tight; it appeas that they just need to allow outbound PPTP access for specific employees who have that need to connect back to your network.

One can connect just fine and their only complaint is that its not very fast, which I expected.
This is expected, especially on that older Firebox III - the VPN throughput on those older WatchGuards isn't that great, resulting in a slow VPN connection. I've seen that many times...