We could actually run a generic clock synchronization protocol to synchronize clocks over a partially synchronous network. I guess paxos kind of builds that in, which adds to its complexity.

Safety in particular doesn't require any timing assumption.

(Note that messages can still be delayed arbitrarily in both protocols)