! Eureka Eureka !
This is not a Pagenavi problem. Even if you disable pagenavi the “previous entry” page will show up 404.
My case was:
My theme was passing in the argument: ‘posts_per_page’=>7
While my wordpress settings ( setting > reading > Blog pages show at most ) was 10
So, wordpress thinks: According to Me there are 10 posts per page so, at 20 posts there is no third page. While the theme thinks, according to me there are 7 posts per page so there is a third page !
Solution:
Match the ‘posts_per_page’=>7 TO the setting > reading > Blog pages show at most = 7 ANd it will FIX !