We'd actually still be okay if you did yyyyMMdd_<timestamp>, which would preserve the current data lexicographically before new data, because yyyyMMdd also increased lexicographically with time.

The important part is that the partition either come last, or be removed entirely because it breaks the ordering.