We have the same problem with 5610's, 5621's, digital sets, other VCM, other IP500, with a phone connected directly to the system through the LAN2 port, using any number of settings or Codecs, used a vlan then a flat network, been on 4.x and 5.x IPOffice, implemented diffserv, or anything else we can think of.
We've noticed that the phones show in the software monitor that they register every 30 seconds or so. We've noticed that tracert's take an unknown hop that times out before finding the phone system. We've noticed that users have problems, not particular handsets. We've tried various/multiple connections for our "problem" users. There is no pattern as to when we have a poor call quality.
We have some IPX on our network. We have HP Procurve PoE switches. Almost all of our phones have a PC hanging off of them with a different subnet for the PC's. Our longest ethernet runs are 150-200 feet. Most of our problems come from there.
Our problems cannot be captured with a recording. We mostly have echo and scratchy-ness that can only be heard on one side of the conversation. It can happen with internal calls or external calls.
We are planning on getting a network assessment ran but I think the problem is so subtle that we won't find anything that way. We've dealt directly with Avaya and their last suggestion was an isolated network.
Maybe we should exchange phone serial numbers as we're almost convinced that we have a bad batch of phones. Some users have complained that messing with the cord can make it happen but we can't reproduce that either.