Without any additional extensions, in Activities Overview search, I do not get to see any recently used files. I am using Gnome 3.6 that ships with Ubuntu 13.04. Is this a feature (or lack of it) or a bug?
This functionality is back in
In Gnome 3.2 this was a feature activated by default and it worked like a charm. Then, in Gnome 3.4 the developers disabled it claiming that it wasn't necessary, since the same functionality was supposedly provided by Gnome Documents. However, Gnome Documents sucks and cannot provide the same functionality.
Of course, you can achieve the same result with a Gnome Shell extension named "Search Recently Used Files", which works OK but is inferior to Unity, since: (a) it shows only files and not folders and (b) it shows only files from the current session, which means that, if you use a file and reboot, this file will not be shown as a recent file.
There is also Synapse, which makes a great job of looking for recent files among other things.
You are absolutely right that it is unacceptable for a modern OS to not be able to provide a fast search in recent files. Actually, this was one of the reasons I am now abandoning Gnome Shell for Unity. Although I like the general concept, Gnome devs are completely unpredictable and may overnight let users hanging. Moreover, they have failed to create a consistent search functionality in the Gnome Shell Overview. I think the direction they have taken in Gnome 3.8 with all search results opening in Gnome Documents is not practical.