Small project that may be of interest to those involved in this discussion: https://github.com/brandtg/alicia

Kind of "eventually monotonic" distributed auto-increment keys. Your mileage may vary.