Here's one that I like,

Radio Shack sells this thing to record conversation over the phone. It's a little adaptor that you insert between the phone and the hand-held part. It has an 1/8" mono output jack. It's cost about 20$ and you can switch the direction of the signal to record your answering messages directly into the phone bypassing the mic of the phone and the room noise that gets into it.
(Dead Link Removed)

-----
zod