WOW! I'm sooooo happy when I receive such deterministic errors.
After saving an account, this message popped up. And you guessed it - it appeared just SOMETIMES!
After a little of SQL profiling i found the reason:
I extended the account's address1_line1 field from 50 to 100 characters. After saving the account, CRM automatically creates/updates also the customeraddress entity.
Extend the customeraddress entity, extend attribute line1, match the length to length of the account address line.