Building on the answer of @paibamboo
He said: Go to: Tools > Options > Projects and Solutions > Web Projects > Use the 64 bit version of IIS Express
My coworker had this box checked (he explicitly looked for it), but had the error message in question. After some hours he unchecked the box and checked it again. Lo and behold: The code now ran with success.
It seems, that there are two places where the state of this box ist saved which became out of sync. Un- and rechecking it synced it again.
Question for more knowledgable users: Was there an update or something last week (for VS 2015) which de-synced the states?