One related idea (to do with pagination itself, not just the pagination controls) I’ve had that I’ve never seen actually implemented:
Where showing n elements per page, if the last page would have no more than ε elements in it, merge it with the previous page.
e.g. n = 10, ε = 2, so a data set of 21 elements might go over two pages of 10 and 11 elements rather than three of 10, 10 and 1.
Sure, SQL LIMIT queries and all that, but it’d tend to be nicer for the user.