After many hours of debugging and despair, the problem is now solved. It turned out to be a very obscure thing.
The redirect is issued by the function ms_load_current_site_and_network() inside /wp-includes/ms-load.php. It was issuing the redirect because /wp-includes/ms-settings.php was not able to set a domain. The reason it was not able to set a domain is because $_SERVER['HTTP_HOST'] was not set.
$_SERVER['HTTP_HOST'] not being set had to do with the PHP setting auto_globals_jit. It was set to On, resulting in the $_SERVER array not being set (as explained in this comment). Even though $_SERVER['HTTP_HOST'] and the rest were defined when loading a single php file with phpinfo(); in it, they were not defined when loading WordPress’s php files. And that led to the redirect.
Setting auto_globals_jit to Off in php.ini resolved it.
Bonus info:
The issue was additionally made more complicated by some form of caching (which I couldn’t pin down or clear). So I had to rely on behavior that I saw occur only once and couldn’t replicate afterwards. For example, I created a separate php file to just check if $_SERVER['HTTP_HOST'] is set – and initially it wasn’t. Following the suggestion from the comment, I used $_SERVER['HTTP_HOST'] twice in the php file – and immediately saw that it was now set. However, when reverting the change and having $_SERVER['HTTP_HOST'] only once in the php file, it still remained set – suggesting I was seeing a cached response. I coulnd’t get it to break again after I fixed it once.
Just documenting this here in case someone encounters similar behavior.