I cycled through once and got no titles. Did the same after half an hour and got the Previous-Next titles. If I hadn't seen this myself, and someone told me that the text of a navigation link becomes the title of a titleless page, and does so only some of the times you'll visit the page, I would have said "no way"!
Unfortunately I'm unable to reproduce the issue in my tests blog, so I cannot tell what's causing this erratic behavior. My only guess is that WP has messed something up (they've been updating things).
I understand you first published those pages with a regular title, to create a proper permalink, then edited them and deleted the titles, right? So, a suggestion: edit them again and paste this in the title field (minus the space between the ambersand and the rest):
& nbsp;
That's the HTML for a space (I had to separate the ambersand from the rest, otherwise you'd get the result instead of the code, i.e. nothing but a blank space). Hopefully this will tell the theme that there is a title there and prevent the wrong thing from creeping in.