Software Update doesn't show available updates OS X 10.8.4 (although this started in 10.8.3). When running Software Update GUI (that switches to App Store), it shows no updates, although some are available (e.g. Java when this was posted originally, or Security Update or Airport Utility later). Running 

softwareupdate --list


returns

Software Update found the following new or updated software:
       * JavaForOSX-1.0
        Java for OS X 2013-004 (1.0), 65205K [recommended]


and then 

sudo softwareupdate --install JavaForOSX-1.0 


installs the update. 

I tried cleaning the Software Update cache, it didn't help.

Any ideas what may be going on and how to fix it? 

Edit: the same problem with Security Update 2013-03and currently with a new update that is available -- Airport Utility.
This sometimes helps me when I know that there is an update: Cmd-R. Since the iTunes/iBooks/Mac App Store are all web-based, it forces a refresh.

Your problem sounds more systemic than this, but it’s a quick thing to check (especially for those Java OS X update which hide from me sometimes).