...In the worst case, for 1 element duplicated N times, then it would be O(N).
yes it is, and for N/2, N/4, ... duplicated elements.
Yes but, it depends on how the duplicates are distributed. For instance, consider N elements and all the duplicates are clustered in, just for example, 4 elements. Accessing any of those 4 elements is basically O(n), while accessing any other element is O(lg N). For such a distribution (granted, it is an unusual one), the big O of the totality is neither O(n) nor O(lg N), for this example it would be (2n + (n - 4) * lg n)
In the specific case of tracking times across the world for what may be a fairly common event, the safe approach is to create an index of distinct unixtimes and bsearch that. No undesirable cases that way.
Anyway, your point that the start of the duplicate list isn't returned by a normal bsearch is definitely valid. I just wanted to point out that, if the duplicates are evenly distributed across the n elements _and_ the ratio of N/duplicates isn't very large (say under 10) then, giving the traditional bsearch "a hand" to find the start of the list is reasonable and, ntdll provides one.
