Welcome to the MongoDB Community @Luke_Coleman!
What sort order are you specifying for your query? It sounds like you are expecting the order of result documents to match insertion order, which is only guaranteed for the special case of a capped collection (see: What is the default sort order when none is specified?).
If you are sorting based on date components as string values, the lexicographic order will be be based on string comparisons (characters and length) as @steevej suggested.
However, it looks like you have a proper date field you could use for sorting (which should also obviate the need to duplicate the data information in various string formats).
To confirm this isn’t an issue with the results returned by your query, you could also try searching for the documents presumed missing from 2016-01-02.
Regards,
Stennie