Does there exist a sorted search with $O(\log n)$ worst-case runtime and $O(\log \log n)$ on average?
Yup.  Do interpolation search, but after $\log n$ iterations, if you haven't found the answer yet, switch to binary search.  This ensures a $O(\log n)$ worst-case running time, while retaining the $O(\log \log n)$ average-case running time.  Note that the average case only applies if you make a particular assumption about the distribution of values in the array.