I am responsible for my company's phone system. We currently have a
NEC Neax 1000 IVS running the phones and voicemail. It is connected to
our local CLEC via a T1. For about a year now various people will tell
us that they cannot reach us via their AT&T cell phones from one side
of the city. Others have problems reaching us from their desk phone.
The usual message is that the phone number has been disconnected,
obviously not a good thing to have said about your company since it
makes us look like we went out of business.

Our CLEC was completely unwilling to help us track down/resolve the
problem, however AT&T was able to test it and found that our CLEC has
not been properly "announcing" our prefix to the outside world. We
finally got the CLEC to fix the problem, however I don't trust them AT
ALL, and was wondering if there is ANY way to test our phone numbers
with every carrier available (and if so how), short of purchasing a
cell phone and land line in every market and doing the testing by
hand.

Although it would probably cost a deal of money and incur serious
downtime, have you considered switching phone companies? Or is this
not possible since the CLEC is the "only game in town" so to speak?
Unfortunatly, I cannot answer your question, but thought I might make
this suggestion.

While not the only game in town they are probably the biggest CLEC
around. The real problem is that I’ve heard nothing but bad things
about almost every other phone company in town (except for Verizon).
We have talked about moving both voice and internet service to other
providers, but we lack the resources at this time to begin such a
move. We are stuck with this telco for the next six months to a year
at least.