diff --git a/openbsc/src/gprs/gb_proxy_patch.c b/openbsc/src/gprs/gb_proxy_patch.c
index c1b88d9..970f2f6 100644
--- a/openbsc/src/gprs/gb_proxy_patch.c
+++ b/openbsc/src/gprs/gb_proxy_patch.c
@@ -335,6 +335,15 @@
 		goto patch_error;
 	}
 
+	if (!tlli_info && parse_ctx->tlli_enc && parse_ctx->to_bss) {
+		/* Happens with unknown (not cached) TLLI coming from
+		 * the SGSN */
+		/* TODO: What shall be done with the message in this case? */
+		err_ctr = GBPROX_PEER_CTR_TLLI_UNKNOWN;
+		err_info = "TLLI sent by the SGSN is unknown";
+		goto patch_error;
+	}
+
 	if (!tlli_info)
 		return;
 
@@ -346,13 +355,6 @@
 			gbproxy_patch_tlli(parse_ctx->tlli_enc, peer, tlli,
 					   parse_ctx->to_bss, "TLLI");
 			parse_ctx->tlli = tlli;
-		} else if (parse_ctx->to_bss) {
-			/* Happens with unknown (not cached) TLLI coming from
-			 * the SGSN */
-			/* TODO: What shall be done with the message in this case? */
-			err_ctr = GBPROX_PEER_CTR_TLLI_UNKNOWN;
-			err_info = "TLLI sent by the SGSN is unknown";
-			goto patch_error;
 		} else {
 			/* Internal error */
 			err_ctr = GBPROX_PEER_CTR_PATCH_ERR;
diff --git a/openbsc/src/gprs/gb_proxy_tlli.c b/openbsc/src/gprs/gb_proxy_tlli.c
index 2074308..4c97f8a 100644
--- a/openbsc/src/gprs/gb_proxy_tlli.c
+++ b/openbsc/src/gprs/gb_proxy_tlli.c
@@ -440,8 +440,8 @@
 	if (parse_ctx->tlli_enc)
 		tlli_info = gbproxy_find_tlli_by_sgsn_tlli(peer, parse_ctx->tlli);
 
-	if (parse_ctx->tlli_enc && parse_ctx->new_ptmsi_enc) {
-		/* A new PTMSI has been signaled in the message,
+	if (parse_ctx->tlli_enc && parse_ctx->new_ptmsi_enc && tlli_info) {
+		/* A new P-TMSI has been signalled in the message,
 		 * register new TLLI */
 		uint32_t new_sgsn_ptmsi;
 		uint32_t new_sgsn_tlli;
@@ -461,46 +461,67 @@
 		LOGP(DGPRS, LOGL_INFO,
 		     "Got new TLLI(PTMSI) %08x(%08x) from SGSN, using %08x(%08x)\n",
 		     new_sgsn_tlli, new_sgsn_ptmsi, new_bss_tlli, new_bss_ptmsi);
-		if (tlli_info) {
-			gbproxy_reassign_tlli(&tlli_info->sgsn_tlli,
-					      peer, new_sgsn_tlli);
-			gbproxy_reassign_tlli(&tlli_info->tlli,
-					      peer, new_bss_tlli);
-			gbproxy_touch_tlli(peer, tlli_info, now);
-		} else {
-			tlli_info = gbproxy_tlli_info_alloc(peer);
-			LOGP(DGPRS, LOGL_INFO,
-			     "Adding TLLI %08x to list (SGSN, new P-TMSI)\n",
-			     new_sgsn_tlli);
 
-			gbproxy_attach_tlli_info(peer, now, tlli_info);
-			/* Setup TLLIs */
-			tlli_info->sgsn_tlli.current = new_sgsn_tlli;
-		}
+		gbproxy_reassign_tlli(&tlli_info->sgsn_tlli,
+				      peer, new_sgsn_tlli);
+		gbproxy_reassign_tlli(&tlli_info->tlli,
+				      peer, new_bss_tlli);
+		gbproxy_touch_tlli(peer, tlli_info, now);
 		/* Setup PTMSIs */
 		tlli_info->sgsn_tlli.ptmsi = new_sgsn_ptmsi;
 		tlli_info->tlli.ptmsi = new_bss_ptmsi;
-	} else if (parse_ctx->tlli_enc && parse_ctx->llc && !tlli_info) {
-		/* Unknown SGSN TLLI */
+	} else if (parse_ctx->tlli_enc && parse_ctx->new_ptmsi_enc && !tlli_info &&
+		   !peer->cfg->patch_ptmsi) {
+		/* A new P-TMSI has been signalled in the message with an unknown
+		 * TLLI, create a new tlli_info */
+		uint32_t new_ptmsi;
+		if (!gprs_parse_mi_tmsi(parse_ctx->new_ptmsi_enc, GSM48_TMSI_LEN,
+					&new_ptmsi)) {
+			LOGP(DGPRS, LOGL_ERROR,
+			     "Failed to parse new PTMSI (TLLI is %08x)\n",
+			     parse_ctx->tlli);
+			return tlli_info;
+		}
+
+		LOGP(DGPRS, LOGL_INFO,
+		     "Adding TLLI %08x to list (SGSN, new P-TMSI is %08x)\n",
+		     parse_ctx->tlli, new_ptmsi);
+
+		tlli_info = gbproxy_tlli_info_alloc(peer);
+		tlli_info->sgsn_tlli.current = parse_ctx->tlli;;
+		tlli_info->tlli.current = parse_ctx->tlli;;
+		tlli_info->sgsn_tlli.ptmsi = new_ptmsi;
+		tlli_info->tlli.ptmsi = new_ptmsi;
+	} else if (parse_ctx->tlli_enc && parse_ctx->llc && !tlli_info &&
+		   !peer->cfg->patch_ptmsi) {
+		/* Unknown SGSN TLLI, create a new tlli_info */
+		uint32_t new_ptmsi;
 		tlli_info = gbproxy_tlli_info_alloc(peer);
 		LOGP(DGPRS, LOGL_INFO, "Adding TLLI %08x to list (SGSN)\n",
 		     parse_ctx->tlli);
 
 		gbproxy_attach_tlli_info(peer, now, tlli_info);
+
 		/* Setup TLLIs */
 		tlli_info->sgsn_tlli.current = parse_ctx->tlli;
-		if (peer->cfg->patch_ptmsi) {
-			/* TODO: We don't know the local TLLI here, perhaps add
-			 * a workaround that derives a PTMSI from the SGSN TLLI
-			 * and use that to get the missing values. This may
-			 * only happen when the gbproxy has been restarted or a
-			 * tlli_info has been discarded due to age or queue
-			 * length.
-			 */
-			tlli_info->tlli.current = 0;
-		} else {
-			tlli_info->tlli.current = tlli_info->sgsn_tlli.current;
+		tlli_info->tlli.current = parse_ctx->tlli;
+
+		if (!parse_ctx->new_ptmsi_enc)
+			return tlli_info;
+		/* A new P-TMSI has been signalled in the message */
+
+		if (!gprs_parse_mi_tmsi(parse_ctx->new_ptmsi_enc,
+					GSM48_TMSI_LEN, &new_ptmsi)) {
+			LOGP(DGPRS, LOGL_ERROR,
+			     "Failed to parse new PTMSI (TLLI is %08x)\n",
+			     parse_ctx->tlli);
+			return tlli_info;
 		}
+		LOGP(DGPRS, LOGL_INFO,
+		     "Assigning new P-TMSI %08x\n", new_ptmsi);
+		/* Setup P-TMSIs */
+		tlli_info->sgsn_tlli.ptmsi = new_ptmsi;
+		tlli_info->tlli.ptmsi = new_ptmsi;
 	} else if (parse_ctx->tlli_enc && parse_ctx->llc && tlli_info) {
 		uint32_t bss_tlli = gbproxy_map_tlli(parse_ctx->tlli,
 						     tlli_info, 1);
diff --git a/openbsc/tests/gbproxy/gbproxy_test.ok b/openbsc/tests/gbproxy/gbproxy_test.ok
index e00c20c..8e6770a 100644
--- a/openbsc/tests/gbproxy/gbproxy_test.ok
+++ b/openbsc/tests/gbproxy/gbproxy_test.ok
@@ -1626,6 +1626,7 @@
   NSEI 4096, BVCI 4098, not blocked, RAI 112-332-16464-96
     RAID patched              (BSS ): 2
     RAID patched              (SGSN): 1
+    TLLI from SGSN unknown          : 1
     TLLI-Cache: 0
 --- Send message from BSS 1 to SGSN, BVCI 0x1002 ---
 
@@ -1743,6 +1744,7 @@
     RAID patched              (SGSN): 2
     APN patched                     : 3
     Attach Request count            : 1
+    TLLI from SGSN unknown          : 1
     TLLI cache size                 : 1
     TLLI-Cache: 1
       TLLI efe2b700 -> efe2b700, IMSI 12131415161718, AGE 0, IMSI matches
@@ -1776,6 +1778,7 @@
     RAID patched              (SGSN): 2
     APN patched                     : 3
     Attach Request count            : 1
+    TLLI from SGSN unknown          : 1
     TLLI-Cache: 0
 --- RA update ---
 
@@ -1821,6 +1824,7 @@
     RAID patched              (SGSN): 3
     APN patched                     : 4
     Attach Request count            : 1
+    TLLI from SGSN unknown          : 1
     TLLI cache size                 : 1
     TLLI-Cache: 1
       TLLI bbc54679/efe2b700 -> bbc54679/efe2b700, IMSI 12131415161718, AGE 0, IMSI matches
@@ -1843,6 +1847,7 @@
     RAID patched              (SGSN): 3
     APN patched                     : 4
     Attach Request count            : 1
+    TLLI from SGSN unknown          : 1
     TLLI-Cache: 0
 --- Bad cases ---
 
@@ -1881,6 +1886,7 @@
     RAID patched              (SGSN): 3
     APN patched                     : 4
     Attach Request count            : 1
+    TLLI from SGSN unknown          : 1
     TLLI cache size                 : 1
     TLLI-Cache: 1
       TLLI efe2b700 -> efe2b700, IMSI (none), AGE 0
@@ -2282,8 +2288,8 @@
     TLLI patched              (BSS ): 8
     TLLI patched              (SGSN): 6
     P-TMSI patched            (SGSN): 2
+    Patch error: other              : 1
     Attach Request count            : 1
-    TLLI from SGSN unknown          : 1
     TLLI cache size                 : 1
     TLLI-Cache: 1
       TLLI c00f7304/ead4775a -> efe2b700/e0543210, IMSI 12131415161718, AGE 0, IMSI matches
@@ -2319,8 +2325,8 @@
     TLLI patched              (BSS ): 9
     TLLI patched              (SGSN): 7
     P-TMSI patched            (SGSN): 2
+    Patch error: other              : 1
     Attach Request count            : 1
-    TLLI from SGSN unknown          : 1
     TLLI cache size                 : 1
     TLLI-Cache: 1
       TLLI ead4775a -> e0543210, IMSI 12131415161718, AGE 0, IMSI matches
@@ -2344,8 +2350,8 @@
     TLLI patched              (BSS ): 10
     TLLI patched              (SGSN): 7
     P-TMSI patched            (SGSN): 2
+    Patch error: other              : 1
     Attach Request count            : 1
-    TLLI from SGSN unknown          : 1
     TLLI cache size                 : 1
     TLLI-Cache: 1
       TLLI ead4775a -> e0543210, IMSI 12131415161718, AGE 0, IMSI matches
@@ -2369,8 +2375,8 @@
     TLLI patched              (BSS ): 11
     TLLI patched              (SGSN): 7
     P-TMSI patched            (SGSN): 2
+    Patch error: other              : 1
     Attach Request count            : 1
-    TLLI from SGSN unknown          : 1
     TLLI cache size                 : 1
     TLLI-Cache: 1
       TLLI ead4775a -> e0543210, IMSI 12131415161718, AGE 0, IMSI matches
@@ -2394,8 +2400,8 @@
     TLLI patched              (BSS ): 11
     TLLI patched              (SGSN): 8
     P-TMSI patched            (SGSN): 2
+    Patch error: other              : 1
     Attach Request count            : 1
-    TLLI from SGSN unknown          : 1
     TLLI cache size                 : 1
     TLLI-Cache: 1
       TLLI ead4775a -> e0543210, IMSI 12131415161718, AGE 0, IMSI matches
@@ -2463,8 +2469,8 @@
     TLLI patched              (SGSN): 9
     P-TMSI patched            (BSS ): 1
     P-TMSI patched            (SGSN): 2
+    Patch error: other              : 1
     Attach Request count            : 1
-    TLLI from SGSN unknown          : 1
     TLLI cache size                 : 1
     TLLI-Cache: 1
       TLLI ead4775a -> e0543210, IMSI 12131415161718, AGE 0, IMSI matches
@@ -2489,8 +2495,8 @@
     TLLI patched              (SGSN): 10
     P-TMSI patched            (BSS ): 1
     P-TMSI patched            (SGSN): 2
+    Patch error: other              : 1
     Attach Request count            : 1
-    TLLI from SGSN unknown          : 1
     TLLI-Cache: 0
 Gbproxy global:
     Invalid Routing Area Identifier : 1