Reproduced with 4.3.0-dev. Something really weird is going on (some reference-stuff?). Making this critical.

this issue is especially nasty when there's an "initiator"
script that does validation of user before it is taken to
the "main" script. if the latter relies on recursion and
checking for instance that a $_SESSION['comingfromscript'] 
is not set (against cut&paste of the URI) before proceeding,
the test will unexpectedly succeed if in a previous
recursion step the $_SESSION['comingfromscript'] has been
assigned to a normal variable even if afterward the
$_SESSION['cominfromscript'] is unset.

On WinNT 4.0 running Apache 2.0.39/PHP 4.2.2 I have seen the same thing.  unset($_SESSION['xyz']) does NOT remove the variable xyz from the session file.  It only kills the instance on the page being processed.  This is an extremely critical problem if other scripts pass what should be "one-shot" values.  The receiving page immediately does an unset thinking that the variable no longer exists ANYWHERE, but if the user does a refresh... poof... the value reappears.
Example snippet:
Script #1

	$_SESSION['manage'] = 'Create';
	echo "<input type=button name='continue' value='Create another?' onClick=\"window.location='pcomanage.php'\">\n";

Script 1 is passing 'manage=Create' to pcomanage.php versus POSTing it, as we may not want the user to be clued to anything by viewing source in the browser.

Script 2

	if (isset($_SESSION['manage'])) {
		$manage = $_SESSION['manage'];
		unset($_SESSION['manage']);
	}

Okay, based on my workflow if the session variable 'manage' is set then I know I'm coming from a script (vs. a POST), so I make a local copy and try to kill the session variable created in Script 1.  No joy!  I have checked the pertinent session file following the processing of the script and 'manage' still appears with it's value (Create).

I have the same problem, running 4.1.1 on FreeBSD, put this script somewhere at your site and run it:

session_start();
echo '<h2>Session just after session_start()</h2>';
echo '<pre>';
print_r($_SESSION);
echo '</pre>';
if(isset($_GET['set'])) {
    $_SESSION['foo'] = 'bar';
    echo '<h2>Session after $_SESSION[\'foo\'] = \'bar\'</h2>';
    echo '<pre>';
    print_r($_SESSION);
    echo '</pre>';
}
if(isset($_GET['unset'])) {
    unset($_SESSION['foo']);
    echo '<h2>Session after unset($_SESSION[\'foo\'])</h2>';
    echo '<pre>';
    print_r($_SESSION);
    echo '</pre>';
}


if($_GET['step'] == 0) {
    echo '<a href="unset.php?step=1&set=1">Next</a>';
}
if($_GET['step'] == 1) {
    echo '<a href="unset.php?step=2">Next</a>';
}
if($_GET['step'] == 2) {
    echo '<a href="unset.php?step=3&unset=1">Next</a>';
}
if($_GET['step'] == 3) {
    echo '<a href="unset.php?step=4">Next</a>';
}
if($_GET['step'] == 4) {
    echo '<p>$_SESSION should be an empty array at this point!</p>';
}

Your (andre@switch.no) sample script does not work for me.  Results look like:
 session just after session_start()

Array
(
)

Next

and the Next link unset.php doesn't exist.  Can you finish your test case please?

unset.php should be the name you save the testscript as...

Final note; we're currently running with register_globals on, while we migrate old code. It seems that this is the reason unset($_SESSION['varname']) won't work. But, the inconsistent behavior (you can assign to $_SESSION but not unset variables from it), is simply intolerable.

Either both:
$_SESSION['varname'] = 'value';
unset($_SESSION['varname']);

work as intended, even with register globals on, or none of them should work. I would prefer them both to work because this will make it much easier to migrate old code while still running with register globals on.

Please try a recent snapshot, of the non-stable kind.  I believe Zeev just fixed this (at least your test case works for me).  

This bug has been fixed in CVS.

In case this was a PHP problem, snapshots of the sources are packaged
every three hours; this change will be in the next snapshot. You can
grab the snapshot at http://snaps.php.net/.
 
In case this was a documentation problem, the fix will show up soon at
http://www.php.net/manual/.

In case this was a PHP.net website problem, the change will show
up on the PHP.net site and on the mirror sites in short time.
 
Thank you for the report, and for helping us make PHP better.