Imagine a large forum topic. The user is just seeking through time. A deep pagination here is when the user knows what they're searching for is more than 1 page away.
The user would have to know a snippet of text or an explicit date range for your search box to help, so what about all the times they don't or if their filters are insufficient? This is why forums have both deep pagination and a search box.
It would be cruel to make the user paginate one page at a time just like it'd be unbearable if Youtube didn't let you jump 10 minutes at a time.
Obviously not every pagination needs deep pagination, but that's between you and your users, and it's what came to mind when I read that article.
What's the use case for that?
I’ve been thinking about it, and ideally one would make a search engine that only indexes pages that have no analytics, tracking, ads, paywalls, etc. Then I’d find those same pages I’m searching for.
To give an example: I found http://blog.deconinck.info/post/2016/12/19/A-Dirt-Cheap-F-Aw... on page 3 of Google for "raspberry pi led", just below https://tech.scargill.net/home-control-2016/ (both of which are interesting IMO)
Google is great for finding things you already know, but I'm using it for discovering things I didn't even know I was interested in.
I can't exactly just put the entire dictionary into google to try and find what I might like. I enter a category I might like, and look through the results matching that category.