" am looking at buying one of these uniden 2355 cordless phones and was hoping someone could confirm for me that they remember everything after a power failure. Particularly the outgoing message for the answering machine as well as any stored incoming messages, address book and phone settings.
"

Yes, I regularly experience power failures (had another last night) and the outgoing message is definitely saved. All address book and phone settings are also saved. Though I can't say for certain, I would also assume that any stored messages are saved too.