It took a year and a half, but I finally catalogued and put away our wine. All 448 bottles: 80% reds, 40% Bordeaux/Cabernet, 50/50 US/French.
There's a lot of bad wine software out there. I looked long and hard for a good web based wine inventory solution before settling on CellarTracker / GrapeStories / cor.kz. I have two specific goals for wine cellar software. It needs to be easy to enter purchases. And it needs to quickly answer questions like "do I have a nice old Bordeaux?" or "where is a cheap Chardonnay for tonight?". It's astonishing how few cellar apps solve those problems. There's iPhone apps that expect you to type in all your wines on the phone! And no app does a great job on the "find a wine" problem. I like CellarTracker best, but some good alternatives are VinCellar and ManageYourCellar.
CellarTracker has been around a long time, it's got a huge community of wine enthusiasts. The website shows its age, you can feel the SQL queries being built up as you navigate the user interface (OTOH, it's very powerful.) There's a more humane user interface in beta now, GrapeStories, which provides a modern AJAXy interface to the same backend database. There's also cor.kz, an iPhone app that also uses your CellarTracker account as the backend. Great for quickly finding a wine without using a computer.
One amazing thing about CellarTracker is the depth of the database. Wine canonicalization is a tricky thing, there's no universal identifier like a UPC or ISBN. So you have to type in "Leroy Vosne-Romanée" and then sift through the seven or so variants to get the right one. They have a great search UI for finding your wine. Only about 7 of my wines were missing, all unremarkable novelty wine. And now that everything is identified I can take advantage of their vast library of tasting notes, recommended drinking dates, pricing, etc.
CellarTracker has a lot of features, I'm just scratching the surface. Bar codes, printed reports, shopping pointers. And I haven't even looked into the community yet. Given how much money is spent on wine you'd think someone would have sewn up the Internet wine market already. With the new UI at GrapeStories I think it may be on its way.
PS: I almost passed on CellarTracker because it stores your password in the clear. That's a pretty terrible sin but they're quite clear on disclosing the problem and the author is remorseful. I finally decided just to use a unique throwaway password for just this site.