One thing I find myself implementing repeatedly is the Union-Find datastructure. I never just need that though. Sometimes I need statistics about the disjoint sets, which inevitably means a custom Union implementation. Sometimes I know more about how often Find will be called, where I can get better performance without doing full path compression.

Another one I've encountered recently is priority queues. Here, memory requirements and operation runtimes depend on which operations are supported -- insert/pop heaps are faster than insert/decrease/pop heaps are faster than insert/update/pop heaps. And if heap operations are your innermost loop on your critical path, you can get huge gains from rolling your own -- because a standard library's priority queue will support whichever operations it supports and you can't pick features a la carte.

But no, I never do this without a search engine handy.

Union-find is one I find needing a fair amount too, although it does make algorithms tricky to debug if the problem is a bad union ("which union was the bad one that caused all these groups to collapse into one?").

But even for these simple data structures, I am much more comfortable implementing them with an algorithm textbook in front of me (or some other resource with similar level of detail), simply because it greatly reduces the scope for implementing the data structure itself incorrectly and, secure in that knowledge, I can focus my debugging on the algorithm itself.