This situation is normal : you need your NSS to be able to page a MS which is in Packet Transfer Mode. GSM was not properly designed with this in mind, so it’s pretty tricky !
You have 2 scenarios :
a) You have an old BSS release which do not support BSS CS PAGING COORDINATION.
b) you have a recent BSS release, and bought the feature BSS COORDINATION
Now, let’s see… 🙂 In case a), the good bet is to upgrade your BSS software. If you can’t do that, then you must install and configure the Gs interface (SGSN-MSC), which will forward your CS PAGING from MSC to SGSN for MS which are in Packet Transfer Mode.
In case b), obviously, just activate the bloody BSS COORDINATION, which will handle transferring the Paging to wherever the MS is.
Gs interface does not provide perfect results.
Bss Coordination : I never tested it myself, but, except possible bugs, there is no reason for it not to work.