PARTIAL SOLUTION FOR THIS ISSUE:
I also had the same issue and I noticed that lookup fields targeting an object which can't be accessed via a tab display automatically all the records.
Example : if, for instance, your lookup field lookup on the standard object Account. Then Only the most recently viewed Accounts will be shown as the standard object Account is being assigned a tab by default.
On the contrary, if your lookup field lookup on a custom object for which any tab has been assigned, then your lookup field will display by default all the records.
If you create later a tab for the custom object which is targeted by the lookup field you have created above then this one will not display all the records anymore but only the most recently viewed.
The opposite applies if you delete the tab.
I hope this help a little bit. I haven't found any documentation describing this behavior however.