Hi Alexia,
From what you described, I think the problem may be with the signalling to your gateway MSC. You said the problem occurs within one city…does this city have its own MSC or BSC? If yes, then check the signalling links between this MSC/BSC and your gateway MSC. Your core network guys will be able to check these for you.
Regards,
SHELDON