If you have not already done so, have someone manually verify each of
the outbound lines being paid for are actually working. I have seen
systems which were not being actively watched slowly have lines fail and
the PBX just puts them as busy until they ran out of lines.
Another thought is to check on the current PBX capabilities and
hardware. There may be unused ports where additional phone lines could
be added to the system.