Does anyone out there have experiences to share about VOIP service providers? Is there software +/- hardware that will allow me to use my computer as an answering machine (with call display info) on regular phone lines?
You can do it without VoIP. Just use a regular MTS phone line and the linux software mgetty/vgetty. You'll have to find an old compatible modem (externals are best) on ebay or something. I've used vgetty with a Cardinal 33.6k external for voice for over 4 years. It is caller ID capable though I don't use it (too cheap). It is also a little tricky to get working, but no worse than any other linux package.
You can have vgetty pass voicemails off to scripts to do whatever you want with the message. I convert them to WAV's on the fly and put them in an incoming folder. You could use it to rename the messages to the caller-id.