Not only PHP5 is affected of this inconsistence - PHP4 behaves different, but still strange.
The text below was intended to be used as user-note for gpc_magic_quotes() (the link for posting the note is broken on php.net), so it might contain quite more information as needed. Nevertheless it should be enough information to discuss the behavior in detail.

If this issue won't be fixed, it should be reclassified as documentation for my taste.

here we go:
------------------------------------

First I expected that keys in submitted gpc-arrays are never escaped.
Anyway. After I saw escaped keys, I assumed they're escaped according to the settings of magic quotes.
... it's even worse...

It took me over 2 days of testing to figure out the exact behavior and creating two functions (one for each php-version) that strips slashes reliably from any array submitted to a script. Hope this saves someones time and nerves.

The following is true for $_GET- and $_POST-arrays. I hope other arrays affected by magic quotes behave equally.
I did not test the behavior for cases where magic_quotes_sybase is set.

== legend for possible case combinations ==
Px = php version we're using
	P4 = php 4.3.9
	P5 = php 5.0.2

MQ = MagicQuotes GPC
	+MQ = magic quotes enabled
	-MQ = magic quotes disabled

TL = TopLevel key
	+TL = key is on top level (i.e. $_GET['myKey'])
	-TL = key is nested within another array (i.e. $_GET['myList']['myKey'])

AK = ArrayKey
	+AK = the value of the key is another array (i.e. is_array($_GET['myKey']) == true)
	-AK = the value is a normal string (i.e. is_string($_GET['myKey']) == true)

== legend for possible results ==
KE = KeyEscaping
	+KE = control chars are prefixed with a backslash
	-KE = key is returned as submitted and needn't to be stripped

VE = ValueEscaping (doesn't apply for array as value)
	+VE = control chars are prefixed with a backslash
	-VE = value is returned as submitted and needn't to be stripped

== here we go - the following rules apply ==
 1) P4 +MQ +AK +TL --> -KE
 2) P4 +MQ +AK -TL --> +KE
 3) P4 +MQ -AK +TL --> -KE +VE
 4) P4 +MQ -AK -TL --> +KE +VE
 5) P4 -MQ +AK +TL --> -KE
 6) P4 -MQ +AK -TL --> -KE
 7) P4 -MQ -AK +TL --> -KE -VE
 8) P4 -MQ -AK -TL --> -KE -VE
 9) P5 +MQ +AK +TL --> -KE
10) P5 +MQ +AK -TL --> +KE
11) P5 +MQ -AK +TL --> +KE +VE
12) P5 +MQ -AK -TL --> +KE +VE
13) P5 -MQ +AK +TL --> -KE
14) P5 -MQ +AK -TL --> -KE
15) P5 -MQ -AK +TL --> +KE -VE
16) P5 -MQ -AK -TL --> +KE -VE
17) The chars '.', ' ' are always replaced by '_' when used in keys.

Example (rule 15):
When running under php 5.0.2 having magic quotes disabled, gpc-keys on top level containing strings are escaped while their associated values are not.

== The following function will strip GPC-arrays for php 4.3.9 ==
function transcribe($aList, $aIsTopLevel = true) {
	$gpcList = array();
	$isMagic = get_magic_quotes_gpc();
	
	foreach ($aList as $key => $value) {
		$decodedKey = ($isMagic && !$aIsTopLevel)?stripslashes($key):$key;
		if (is_array($value)) {
			$decodedValue = transcribe($value, false);
		} else {
			$decodedValue = ($isMagic)?stripslashes($value):$value;
		}
		$gpcList[$decodedKey] = $decodedValue;
	}
	return $gpcList;
}

== The following function will strip GPC-arrays for php 5.0.2 ==
function transcribe($aList, $aIsTopLevel = true) {
	$gpcList = array();
	$isMagic = get_magic_quotes_gpc();
	
	foreach ($aList as $key => $value) {
		if (is_array($value)) {
			$decodedKey = ($isMagic && !$aIsTopLevel)?stripslashes($key):$key;
			$decodedValue = transcribe($value, false);
		} else {
			$decodedKey = stripslashes($key);
			$decodedValue = ($isMagic)?stripslashes($value):$value;
		}
		$gpcList[$decodedKey] = $decodedValue;
	}
	return $gpcList;
}

Usage:
$unstrippedGET = transcribe($_GET);
$unstrippedPOST = transcribe($_POST);

Maybe someone is willing to test those combinations for other php-versions and with magic_quotes_sybase set to 'on' - let me know.
Sorry for this huge amount of text, but its complete. I was unable to compress the the decision table more than this.

-----------------

Duplicate of bug #29165 (reported earlier than this, note about this report added there)