Thank you for your interest in NATS Streaming.
Yes, sequence numbers on a given channel are monotonically increasing. However, there are cases due to message limits (count/size/age) that old messages get discarded. So it could be possible for a subscriber to get some messages from the beginning of the log, subscriber go down, some of the messages at the beginning of the log being removed due to limits, and the subscriber on restart would then see a gap.
The timestamp is assigned by the server, and as for sequence numbers, on a given channel the timestamp will be also monotonically increasing. For the starting point, you can use sequence and/or time, with, as you said, the caveat that server and clients may not have the exact same view of time.
When a durable subscription restarts, or if the server restarts while subscribers (durable or not) were still running, a redelivery of non-acknowledged messages occurs. If a subscriber is stalled (server sent up to MaxInflight messages without receiving an ack), the redelivery is postponed up to 3 times the AckWait interval. This may cause a subscriber to start receiving "new" messages and then a batch of old unacknowledged messages (see
https://github.com/nats-io/nats-streaming-server/issues/187). I plan to change that to make redeliveries always ignore the fact that MaxInflight messages were already sent.
That being said, with message redeliveries, there will always be out-of-order delivery. Suppose you receive messages 1, 2, 3, 4 and 5, and don't ack message 1 and 2 right away. New messages come in, say 6, 7 and 8. The the redelivery timer kicks in and messages 1 and 2 are redelivered. From an application perspective it may seem that they are out-of-order, but they are simply redelivered.
Hope this helps.
Ivan.