I somehow missed the preceding discussion, so I'll comment on what I've seen so far.
I think the most reasonable default is O(1) for lookup and O(n) for extension, like in Nikita Volkov's record package. It is quite unfortunate that this package limits the number of fields! If GHC would offer generic support for tuples of arbitrary size (with the same efficiency as today) this limitation could be avoided and all would be well.
Currently "record" is limited to up to 24 fields. However it was just an arbitrary number that I've chosen. No part of GHC limits us to that number. The only reason I'm not introducing bigger arities is that unfortunately the compilation time of the "record" library grows exponentially in relation to the highest arity supported. I expect, that limitation could be lifted once/if the ideas behind the library get implemented as an extension to GHC.