But that might, indeed, be the answer to your question.... The fact that it works 75% of the time but not the other 25% may well be a product of load on any part of the system between the client and the printer. You may have reached "saturation" somewhere along the line and no matter what you do on the client or printer end will give you the results you desire.

Could you organize a Terminal Services connection to the inside and try printing through that? It might work better since I don't think the print job would kick off from the terminal server until it is properly spooled at the remote location... Then it would be like being on the local network without the VPN overhead.