Now that Updates.com is gone, what other options do we have to check to make sure our software is up-to-date?

I guess you could use the same method I have been using for years, go to the vendor's site and check for updates.
There are other solutions, such as Cnet's recommendation of subscribing to their download dispatch newsletter, which will tell you of updates and upgrades as they become available, though you may have to sift through a lot of stuff you don't use to get to what you need.

Did you ever find another tool to replace updates.com? I have looked for a couple of years now and have found nothing! I would love a tool like this. I used to use it all the time!

You could try BigFix
http://www.georgedillon.com/web/freeware/bigfix.shtml

I don't know the updates.com program, so I don't know either if BigFix is similar or close even.