Thanks all for your replies and helpful suggestions,

There will be multiple directories (but I will only be concerned with one at a time), the one that I will be using will be specified, and this may have up to 50,000 files in the one directory. This is the most that we have ever seen in one directory, but it is normally more like 1000. I do want to plan for the worst case scenario though. Unfortunately a file and directory naming sturcture like what you are suggesting is not an option, as this will be specified by the client.

I ran gaff's code from above and found it to be a reasonable speed. Perhaps a little slow when tested against 50,000 files but I only ran it on this slow machine.

The only other idea that I had was to keep a record of the oldest file in a text file, and then this will only need to be updated when a file in that directory is deleted, or more to the point when that particular file is deleted. So I could return a response to the client, and then continue on with finding the oldest file, in the background...
Any thoughts?