So yeah, I still connect to the Internet through a modem... Anyway, I built a new PC a couple of months ago, and was connecting to the internet through the old computer, using a proxy. I've been trying to find a voicemodem, so I can replace my uber-crappy answering machine.
I went to Best Buy to see what they had, and ended up picking out a generic voicemodem for ~$35, which has actually been working pretty well (in Windows). The included program, Supervoice, is capable (multiple mail boxes, fax capability, etc) but pretty ugly, and makes you exit before you dial the Internet. Andrew pointed me to IVM, which is very nice and has a lot of great options. I'm currently testing it out, and trying to decide if it's worth the $68 for the 3 OGM 8 Mailbox version (there's also a $20 version with no menus). It probably is, just so we don't have to remember to restart Supervoice when we get off the internet.
I couldn't find any free voicemail software for Windows.
UPDATE: I just called home and got the machine, and man does IVM sound nice. I recorded the message through my Shure SM57 into my Audigy 2 Platinum, max quality. Supervoice only allows 8-bit files, and totally bugged out when I tried to use the higher quality one. IVM allows you to use higher quality files, and I think that clinches my decision. Even if I just get the 1 OGM 1 Mailbox version, I'll be buying IVM soon.