In Model/Express/Checkout.php the returnFromPaypal($token) function includes this:
$shippingAddress->setLastname(null);
If I remove this, I can change the _exportAddressses function in Model/Api/Nvp.php to include
'firstname' => $data['FIRSTNAME'], 'lastname' => $data['LASTNAME'],
instead of
'firstname' => $data['SHIPTONAME'],
This will properly assign first- and lastname to their respective fields. I am still trying to figure out, why Magento is assigning the full name to the firstname field in the first place - and why nobody is bothered by this...