If anyone else stumbles upon this:
The problem is caused by a missing value for the
prefix field on customer entity level, not customer address entity.
When activating and requiring the "prefix" field in a shop where there are already existing customers those won't have any value stored for the
prefixattribute for either customer entity nor customer address entity.
During checkout the customer can choose to create a new address and enter a value for the now required
prefix attribute there but the value will still be missing for the customer entity leading to the error described above.
The only way to fix this is to either set the
prefix attribute to not be required in the admin interface or assign a value to the
prefix attribute for each customer (for example via a simple php script).