Keychain integration is broken in Safari
The problem is solved. Unfortunately I've done so many things that I don't know what solved it.

Here are some things I did. These steps should be safe but in any case before starting either make sure your time backup is on and/or make a backup of your Keychains folder in ~/Library:


Remove / re-add the keychains
I disabled iCloud and re-enabled it again (and rebooted in the mean time) (I suspect this was part of the solution)
I cleared Safari history data (although I'm pretty sure this didn't have any effect)
I toggled the Safari preferences to remember passwords (for sure this was not the solution but might have helped in combination with iCloud reset)


Some things I did but where you should be a bit more cautious about: 


In ~/Library/Keychains: I deleted a folder called F1090786-29BB-5136-A02B-7266FEF0DD9A (actually moved to tmp location) (found somewhere on the apple community sites)
I removed ~/Library/Preferences/com.apple.security.plist (again: I actually moved it away)