Another follow-up:
The pull-request with the fix & a new test is now out for review: https://github.com/letsencrypt/boulder/pull/3113
I’ve also posted an API announcement to indicate that we are unfortunately not going to be able to fix this bug in production until next week: Update Registration/Key Rollover Temporarily Unavailable
@letharion, @moritz - Thank you both again for reporting the problem and helping diagnose the cause.