Understanding an unknown digital encoding
To answer my own question:

This coding turned out to encode 4 bits in 5 symbols, similar to what @MrSnrub suggested. Following is the full encoding table (using H and L for for high- and low- voltage levels, to avoid confusion between decoded bits and symbols as suggested by @Justin. A pair of voltage levels forms one symbol).

The symbols (+) and (-) show symbols when polarity has been inverted - both decode to the same bits.

decode   symbols (+)       symbols (-)
======   ==============    ==============
0000     LH LL HH LL HH    HL HH LL HH LL 
1000     LH LH LL HH LL    HL HL HH LL HH 
0100     LH LL HL HH LL    HL HH LH LL HH 
1100     LH LH LH LL HH    HL HL HL HH LL 
0010     LH LL HH LH LL    HL HH LL HL HH 
1010     LH LH LL HL HH    HL HL HH LH LL 
0110     LH LL HL HL HH    HL HH LH LH LL 
1110     LH LH LH LH LL    HL HL HL HL HH 
0001     LH LL HH LL HL    HL HH LL HH LH 
1001     LH LH LL HH LH    HL HL HH LL HL 
0101     LH LL HL HH LH    HL HH LH LL HL 
1101     LH LH LH LL HL    HL HL HL HH LH 
0011     LH LL HH LH LH    HL HH LL HL HL 
1011     LH LH LL HL HL    HL HL HH LH LH 
0111     LH LL HL HL HL    HL HH LH LH LH 
1111     LH LH LH LH LH    HL HL HL HL HL 


This table can in fact be derived using a simple state diagram (shown here for positive polarity), similar to that I showed in my question. The crucial piece of information that I was missing was the fact that the state diagram gets reset to state LH every 4 encoded bits and an extra symbol inserted into the stream.



These encoder resets on 4 bit boundaries were the cause of ambiguous transitions to LH that were puzzling me. I found this out by using a representation of the symbols similar to what @Justin suggested. When displaying encoded symbols in that more compact way it became immediately obvious that the code is based around 5 symbol blocks.

So basically I was mislead by my early assumption that bit encoding wasn't dependent on bit position (the lookup table I mentioned in my question was constructed without considering any alignment). My poor understanding of the upper layer protocols also led me to dismiss the extraneous 1 bits in the decoded stream which in hindsight obviously appeared in every 5th position when using the naive decoding algorithm I mention in the second paragraph of my question.

I can only speculate why this specific code was chosen over something more common like differential Manchester. One benefit seems to be that it's very easy to detect errors in transmission. Since 10 voltage levels encode only 4 bits there are plenty of invalid combinations that the decoder can detect as line errors. At first glance the encoder resets seem to aid synchronization to 4-bit boundaries, but in fact they aren't that useful. In this code LH LH LH LH LH LH LH ... (long sequence of 1s) is a valid sequence and in such a sequence it's impossible to detect the 4-bit boundaries.