I don't see how it could possibly be the PM. The modems negotiate speed
themselves - the PM has nothing at all to do with it.
It is conceivable that the modem could get locked to a 9600 rate to
the PM, and not negotiate anything above that, but it would be consistent.
*No one* would get over 9600 on that modem.
You say your telco swears its not the lines. Are you *sure* they've been
tested? Have you put a phone on there and actually listened for noise?
It wouldn't be the first time a telephone company has lied to an ISP!