"must I replace the wall wart, which will be a problem. The answering machine is new. Doubt if there is any warranty however. "
Warranty wouldn't help you... unless you're willing to undertake an expensive and lengthy legal battle to get conducted/radiated RFI emissions standards for consumer gear tightened up and enforced ;-)
If you wanted to replace the wall wart, you wouldn't want to replace it with another one from the same company anyway. It's not broken, it's just poorly designed.
A lot of people have had success replacing these noisy switching power supplies with good old linear 60Hz transformer supplies...
you might be able to find one at Radio Shack, but you have to be careful not to buy another cheap switcher there. But if you're sure it's the wall wart, not the phone, and you really want to easily dispense the problem, this is the way to go... if you happen to have a 12V @ 600mA wall wart around, you can use an LM317 regulator to drop that to 7.5V and you'll have a nice quiet supply for your phone.
I'd recommend toroidal chokes on the cord but from what you've described it sounds like just having the wall wart plugged in causes the noise all throughout the house ... so it sounds like you need a filter on the AC input side. You could buy an RFI-filtered power strip to plug the wall wart into and see if that helped, but honestly, replacing the supply with an older junk-box wall wart with a regulator tacked on might be cheaper.
Good info on tackling RFI here:http://audiosystemsgroup.com/RFI-Ham.pdf