For the problem mentioned in the post (determining whether a given password is valid), how about using a Trie[0]? Wouldn't this work perfectly in this situation?
The quest for a sublinear algorithm is futile in the face of caching. The solution is similar to the solution to branch-based timing attacks: don't branch, in code or in data. Every comparison must follow the same code path and the same memory path, and that means reading every element of the data structure every time you search.