search on 'open' dialog is out-of-date

The Recently Used list you referring to is stored as an xml file ~/.local/share/recently-used.xbel. Following is an example

<?xml version="1.0" encoding="UTF-8"?>
<xbel version="1.0"
      xmlns:bookmark="http://www.freedesktop.org/standards/desktop-bookmarks"
      xmlns:mime="http://www.freedesktop.org/standards/shared-mime-info"
>
  <bookmark href="file:///home/Usename/Firewall/fwbuilder.fwb" added="2012-11-07T04:33:55Z" modified="2012-12-20T05:31:26Z" visited="2012-11-07T04:33:55Z">
    <info>
      <metadata owner="http://freedesktop.org">
        <mime:mime-type type="application/octet-stream"/>
        <bookmark:applications>
          <bookmark:application name="fwbuilder" exec="&apos;fwbuilder %u&apos;" modified="2012-12-20T05:31:26Z" count="4"/>
        </bookmark:applications>
      </metadata>
    </info>
  </bookmark>
  <bookmark href="file:///home/Usename/Desktop/limit_test.py" added="2012-12-16T04:48:29Z" modified="2012-12-16T06:02:28Z" visited="2012-12-16T04:48:30Z">
    <info>
      <metadata owner="http://freedesktop.org">
        <mime:mime-type type="text/x-python"/>
        <bookmark:groups>
          <bookmark:group>gedit</bookmark:group>
        </bookmark:groups>
        <bookmark:applications>
          <bookmark:application name="gedit" exec="&apos;gedit %u&apos;" modified="2012-12-16T06:02:28Z" count="16"/>
        </bookmark:applications>
      </metadata>
    </info>
  </bookmark>
  <bookmark href="file:///home/Usename/Firewall/gateway.int.apple.com.fw" added="2012-12-20T05:32:03Z" modified="2012-12-20T05:35:25Z" visited="2012-12-20T05:32:03Z">
    <info>
      <metadata owner="http://freedesktop.org">
        <mime:mime-type type="application/x-shellscript"/>
        <bookmark:groups>
          <bookmark:group>gedit</bookmark:group>
        </bookmark:groups>
        <bookmark:applications>
          <bookmark:application name="gedit" exec="&apos;gedit %u&apos;" modified="2012-12-20T05:35:25Z" count="3"/>
        </bookmark:applications>
      </metadata>
    </info>
  </bookmark>
</xbel>

It is a facility/feature of the GTK+ library/framework.

The reason of inconsistency between software, including software using GTK+, is because author of individual package/software may choose to use or not use it. There is no law/rule to enforce that. Some author may choose to not provide a recent list in their software. Some may implement their own. Some may use it with filter for file type(file extension).

There is no right or wrong about this. This also happen to software running on other OS, not only Linux.