I have (/had) the same issue:
If I use the old interface in Outlook, no indexing past a certain date.
But using the "new Outlook" (interface) it seems to be searching all mails correclty and indexing as it should.
This seems to be a Microsoft problem. Now if only the new interface was as user friendly as the old...