Steps to reproduce:
Click to open any window with big amount of records (where page navigation buttons should appear)
In Lookup Record enter query to select one or few records (amount of records in result should be less than page capacity)
Go to Grid view
You will see no navigation buttons in this case. I'm talking about first page, previous page, next page and last page. It's okay.
Open Lookup Record and empty all fields to show all records
You will see all records but still NO navigation buttons. In this case they should be there.
Workaround: navigating out of the window (i.e. to Home tab) when returning to the window the page navigation appears.
This is not reproducible in version 6.2, maybe it was fixed.