Intermittent access via itnernet, VPNs, and NAT

This one has me stumped. We have a private network that is connected to the Internet.  The configuration is:

Internet feed connects via my Providers switch to a fiber connection to my POP.
At the POP, the fibre media converter connects to an additron switch.
Additron connects to a Netscreen Firewall/VPN/NAT device.
The netscreen connects to a Cisco 2900 XL switch (SW1).
The SW1 then connects a (new)email server and on to other switches and end users on the network

The problem is mainly to connect to the email server which is assigned both a private IP and a Public IP (NATed by the Netscreen.

I am testing the email remotely from another city and have a working VPN tunnel into the netwscreen to access the private IP addresses.

THE PROBLEM
Pinging the provider's switch (the entry point into my network) - I lose about 50% of all packets (thousands of pings)
However, if I connect via the VPN, I can ping a device inside the network using its private IP address with no problem - less than 2% loss.
Sometimes it takes several tries to establish the VPN tunnel but, once connected, it works perfectly.
Other locations seem to have lower loss to the Provider's swicth so I suspected my local connection - but this does not explain why the VPN works so well. The provider claims he can ping his switch with no loss from multiple locations.

Finally, although we once had a conenction to the email server, we cannot log on to it at all now.

I need to activate this server soon and this connectivity issue has stopped us dead.

Thanks.