Perhaps try to increase your MaxTotalThreads from default of 40 decimal to 80 decimal. This might just be a band aid however, as I believe the issue to be latency over the VPN links.
What is your ping time from your BES to your Domino mail servers over the VPN? If you can't ping how about NotesConnect (nPing)?
Are your VPN users mailfiles increasing greatly? That could explain the issues now vs before. Scanning large mailfiles can be intensive over our high speed low latency WAN links within the US, I can't imaging doing that over a VPN link overseas.
I really think the ultimate solution is to set up an additional BES VM in the US connecting via WAN or LAN links to the mailboxes in US / CA.
BESX 4.1.7 on Exchange 2003: 65 Devices
BESX 5.0.3 on Exchange 2003: 2007 Devices