Why does the OS X Software Update check take so long?
Mac OS X keeps a list of all installed packages in /var/log/receipts.

When software update is run it checks for updates for every (or perhaps only Apple) package individually by sending a HTTP request with a signature of the package to Apple's servers and waiting for a reply. This is necessary because of the wide variety of configurations possible for any system.

On my Snow Leopard system running software update sent ~322 HTTP requests to Apple's servers.

So basically it is just looking up if there are any updates, but because of the sheer number of separate and sometimes optional (Java, X11, printer drivers, etc.) packages, combined with the fact that it's sending each request separately, it can take awhile.