Hello,
what is the bandwidth available on the leased lines? You could have jitter problems caused by large data packets blocking voice packets. Link fragmentation and interleaving (LFI) would help then.
How did you check load on the lines? "show interface" might not reveal anything, because the load interval is at least 30 seconds, but VoIP degradation is possible even with 1 second load peaks.
Enable LLQ for VoIP at the leased lines in any case, you WILL need it.
Do not forget about LAN switches, priority queueing is recommended there as well.
And implement call admission control to limit the number of concurrent VoIP connections to what your priority queue can handle.
So in brief:
1) if bandwidth anywhere lower than 768 kbps the use LFI
2) use LLQ on every interface VoIP traffic is present ("auto qos voip" is a good starting point.)
3) priority queueing for VoIP in LAN switches
4) Call admission control.
Hope this helps! Please rate all posts.
Regards, Martin