I have a Winbond ISD4002 I intend to hook to a PIC (someday!). This has SPI interface, and can have multipule messages. It is available with different recording times. All you have to do is connect a microphone and a speaker, so they say!

Dave