diff --git a/src/bts_pch_timer.c b/src/bts_pch_timer.c
index 20373ac..312d85a 100644
--- a/src/bts_pch_timer.c
+++ b/src/bts_pch_timer.c
@@ -26,8 +26,22 @@
 #include <gprs_debug.h>
 #include <gprs_pcu.h>
 #include <bts_pch_timer.h>
+#include <gprs_ms.h>
 
-static struct bts_pch_timer *bts_pch_timer_get(struct gprs_rlcmac_bts *bts, const char *imsi)
+static struct bts_pch_timer *bts_pch_timer_get_by_ptmsi(struct gprs_rlcmac_bts *bts, uint32_t ptmsi)
+{
+	struct bts_pch_timer *p;
+	OSMO_ASSERT(ptmsi != GSM_RESERVED_TMSI);
+
+	llist_for_each_entry(p, &bts->pch_timer, entry) {
+		if (p->ptmsi != GSM_RESERVED_TMSI && p->ptmsi == ptmsi)
+			return p;
+	}
+
+	return NULL;
+}
+
+static struct bts_pch_timer *bts_pch_timer_get_by_imsi(struct gprs_rlcmac_bts *bts, const char *imsi)
 {
 	struct bts_pch_timer *p;
 
@@ -57,29 +71,46 @@
 	bts_pch_timer_remove(p);
 }
 
-void bts_pch_timer_start(struct gprs_rlcmac_bts *bts, const char *imsi)
+void bts_pch_timer_start(struct gprs_rlcmac_bts *bts, const struct osmo_mobile_identity *mi_paging,
+			 const char *imsi)
 {
-	if (bts_pch_timer_get(bts, imsi))
+	struct bts_pch_timer *p;
+	struct osmo_tdef *tdef;
+
+	/* We already have a timer running for this IMSI */
+	if (bts_pch_timer_get_by_imsi(bts, imsi))
 		return;
 
-	struct bts_pch_timer *p;
 	p = talloc_zero(bts, struct bts_pch_timer);
 	llist_add_tail(&p->entry, &bts->pch_timer);
-	osmo_strlcpy(p->imsi, imsi, sizeof(p->imsi));
 	p->bts = bts;
+	OSMO_STRLCPY_ARRAY(p->imsi, imsi);
+	p->ptmsi = (mi_paging->type == GSM_MI_TYPE_TMSI) ? mi_paging->tmsi : GSM_RESERVED_TMSI;
 
-	struct osmo_tdef *tdef = osmo_tdef_get_entry(the_pcu->T_defs, 3113);
+	tdef = osmo_tdef_get_entry(the_pcu->T_defs, 3113);
 	OSMO_ASSERT(tdef);
 	osmo_timer_setup(&p->T3113, T3113_callback, p);
 	osmo_timer_schedule(&p->T3113, tdef->val, 0);
 
-	LOGP(DPCU, LOGL_DEBUG, "PCH paging timer started for IMSI=%s\n", p->imsi);
+	if (log_check_level(DPCU, LOGL_DEBUG)) {
+		char str[64];
+		osmo_mobile_identity_to_str_buf(str, sizeof(str), mi_paging);
+		LOGP(DPCU, LOGL_DEBUG, "PCH paging timer started for MI=%s IMSI=%s\n", str, p->imsi);
+	}
 }
 
-void bts_pch_timer_stop(struct gprs_rlcmac_bts *bts, const char *imsi)
+void bts_pch_timer_stop(struct gprs_rlcmac_bts *bts, const struct GprsMs *ms)
 {
-	struct bts_pch_timer *p = bts_pch_timer_get(bts, imsi);
+	struct bts_pch_timer *p = NULL;
+	uint32_t tlli = ms_tlli(ms);
+	const char *imsi = ms_imsi(ms);
 
+	/* First try matching by TMSI if available in MS */
+	if (tlli != GSM_RESERVED_TMSI)
+		p = bts_pch_timer_get_by_ptmsi(bts, tlli);
+	/* Otherwise try matching by IMSI if available in MS */
+	if (!p && imsi[0] != '\0')
+		p = bts_pch_timer_get_by_imsi(bts, imsi);
 	if (p)
 		bts_pch_timer_remove(p);
 }
diff --git a/src/bts_pch_timer.h b/src/bts_pch_timer.h
index 26b89c8..3e47161 100644
--- a/src/bts_pch_timer.h
+++ b/src/bts_pch_timer.h
@@ -32,11 +32,15 @@
 	struct llist_head entry;
 	struct gprs_rlcmac_bts *bts;
 	struct osmo_timer_list T3113;
+	uint32_t ptmsi; /* GSM_RESERVED_TMSI if not available */
 	char imsi[OSMO_IMSI_BUF_SIZE];
 };
 
-void bts_pch_timer_start(struct gprs_rlcmac_bts *bts, const char *imsi);
-void bts_pch_timer_stop(struct gprs_rlcmac_bts *bts, const char *imsi);
+struct GprsMs;
+
+void bts_pch_timer_start(struct gprs_rlcmac_bts *bts, const struct osmo_mobile_identity *mi_paging,
+			 const char *imsi);
+void bts_pch_timer_stop(struct gprs_rlcmac_bts *bts, const struct GprsMs *ms);
 void bts_pch_timer_stop_all(struct gprs_rlcmac_bts *bts);
 
 #ifdef __cplusplus
diff --git a/src/gprs_bssgp_pcu.c b/src/gprs_bssgp_pcu.c
index 0dd6cdc..424a381 100644
--- a/src/gprs_bssgp_pcu.c
+++ b/src/gprs_bssgp_pcu.c
@@ -39,6 +39,7 @@
 #include "tbf_dl.h"
 #include "llc.h"
 #include "gprs_rlcmac.h"
+#include "bts_pch_timer.h"
 
 /* Tuning parameters for BSSGP flow control */
 #define FC_DEFAULT_LIFE_TIME_SECS 10		/* experimental value, 10s */
@@ -319,7 +320,9 @@
 
 	/* FIXME: look if MS is attached a specific BTS and then only page on that one? */
 	llist_for_each_entry(bts, &the_pcu->bts_list, list) {
-		gprs_rlcmac_paging_request(bts, &paging_mi, pgroup);
+		if (gprs_rlcmac_paging_request(bts, &paging_mi, pgroup) < 0)
+			continue;
+		bts_pch_timer_start(bts, &paging_mi, mi_imsi.imsi);
 	}
 	return 0;
 }
diff --git a/src/gprs_rlcmac.cpp b/src/gprs_rlcmac.cpp
index 22b12df..ffa656c 100644
--- a/src/gprs_rlcmac.cpp
+++ b/src/gprs_rlcmac.cpp
@@ -26,7 +26,6 @@
 #include <pcu_l1_if.h>
 #include <gprs_rlcmac.h>
 #include <bts.h>
-#include <bts_pch_timer.h>
 #include <encoding.h>
 #include <tbf.h>
 #include <gprs_debug.h>
@@ -49,7 +48,6 @@
 		return -1;
 	}
 	bts_do_rate_ctr_inc(bts, CTR_PCH_REQUESTS);
-	bts_pch_timer_start(bts, mi->imsi);
 	pcu_l1if_tx_pch(bts, paging_request, plen, pgroup);
 	bitvec_free(paging_request);
 
diff --git a/src/tbf_ul.cpp b/src/tbf_ul.cpp
index 1d06e53..0282122 100644
--- a/src/tbf_ul.cpp
+++ b/src/tbf_ul.cpp
@@ -443,7 +443,7 @@
 					  "Decoded premier TLLI=0x%08x of UL DATA TFI=%d.\n",
 					  new_tlli, rlc->tfi);
 				update_ms(new_tlli, GPRS_RLCMAC_UL_TBF);
-				bts_pch_timer_stop(bts, ms_imsi(ms()));
+				bts_pch_timer_stop(bts, ms());
 			} else if (new_tlli != GSM_RESERVED_TMSI && new_tlli != tlli()) {
 				LOGPTBFUL(this, LOGL_NOTICE,
 					  "Decoded TLLI=%08x mismatch on UL DATA TFI=%d. (Ignoring due to contention resolution)\n",