Network Connectivity... Dealing with Providers

Semi off-topic... I have a client using an unnamed provider right now. My throughput to my client is horrible, their connection is horrible, their provider swears its not them... I can traceroute and ping till I'm blue in the face and show data to the provider (who thinks packet loss is not that big of a deal) but it seems to be getting me nowhere... What steps, methods, and or tools has anyone else used for monitoring connectivity. I have 3 ways of connecting to my client via Verio, Level3, and GBLX I plan to test all of my locations. Sometimes one of my connections gets stuck but the others work, other times all my connections fail... I segmented it to one of 3 routers in my clients path but I want to be fair to their provider so I'm looking to do some UNBIASED testing. So far I'm thinking bing, iperf, and some traceroutes but I wanted to get an overall view perhaps of something someone else has done that has helped them.

Anyone care to discuss their methods or tools for dealing with a situation like this? ... I'm not in the ISP field anymore (VoIP now) so I stand nothing to gain/lose by pointing out a flaw in the provider... I just want my clients network to normalize at this point instead of having to wait until their provider's routers decide they actually want to forward packets instead of letting them roam around who knows where...

Thanks in advance ... And definitely no need for the off-topic police to start a thread on how off topic this is... (Hence the intro)