Sorry, forgot to move it.
It is fixed now.
One caveat. It has problems with column sorts. It only sorts the current page. That is a fundemental problem with paginate.
I have written a new version from scratch that I am using in production, it just needs to add a few missing features and I will upload it to contrib/