Sequence numbers are in the inputs, not the outputs. Satoshis plan for letting you change fees after broadcast would be very hard to implement by his own admission.
Yes, if you pay for 100THash of work it's possible you won't actually ever make it into a block, if you get very unlucky. Perhaps miners would sell "additional work after first block inclusion" or some other slightly different model. I'm not sure yet.