So I've gotten to the bottom of this issue, and there were three causes for my confusion:
First, if you don't set a path= parameter for the cookie, IE3 will assume that the cookie is for this exact path only. This means that it will send back the same cookie when accessing /test.php again, but nowhere else on the site.
The solution is to include path=/ when setting the cookie.
Second, IE3 does not recognize cookies without an Expires parameter. The solution is to include Expires= in the Set-Cookie header, in "standard" cookie format.
The third is caused by the new Max-Age parameter, helpfully added by PHP for some reason, which IE3 does not recognize. Instead, it assumes everything up to and including Max-Age is the cookie name.
The solution is to set the cookie using PHP's header() function instead, like so:
header('Set-Cookie: test2=hi; expires=Tue, 02-Feb-2021 04:20:00 GMT; path=/');
(In this case, test2 is the name of the cookie, hi is the contents, and it expires about a year from today, on Feb 2nd.)