Okay, here is my analysis:

I've enabled the debug output of the database, by setting
the following in demo/config.ini: 
  level = DEBUG

Actually I could reproduce this quite often with the local database.
The log with my first run is in bad_run.txt,
then I've rectified the debugging output and added some more,
see my hg export 
  issue2550731-better-debugging-20130105ber1.patch
which is on top of John's "test" environment, but you'll get the idea.
This resulted in bad_run2.txt, where I did at least see one race condition.
In function set_inner() the previous node is the same both times,
this is because it is read before the first change is made to it.
See my comments within bad_run2.txt.
Looks like this needs some better locking during the transaction:
Once you read with the intention to update, you need to block other processes 
with the same goal.

It may not be the only problem, thought. I haven't fully groked set_inner() yet,
it feels a bit suspicious to me that the journal value is getting the old one and 
keeping it for String as well. Other types change it. But if this is broken, then a lot 
more history for strings would not work in all cases, which seems unlikely.