I have a KX-TCD735E. I bought it in England, and I'm in the states.
And I don't have the manual. Almost unbelievably, I cannot work out
how to record a new outgoing message (i.e. the one that usually says
'I can't take your call right now, please leave a message'. What I
would like are coherent instructions on which buttons to press to make
it happen.

This model is a cordless handsfree anserphone, and has buttons with
record,  stop, play. I think they are the same as a lot of recent
panasonic models. You can see this one at
http://www.panasonic.co.uk/product/dectphone/KXTCD735EMC.htm

Hello there!

I believe that I've found the answer you've been looking for. After
looking through the support section of the Panasonic UK site, linked
to from the above link, I stumbled upon the manual for your phone. It
can be downloaded at:
 http://www.support.panasonic.co.uk/sys/ttips/Panasonic/Communication_Products/Dect/KX/TCD735/KXTCD735.pdf
(You should right click on the link and click Save Target As to save a
copy to your computer)

Detailed instructions on how to record a new outgoing message can be
found on page 78 of the manual, but I'll list the simplist way here
for you:

1. Press INT then #
2. Press 7 and then 6
3. Record your message, press 9 when you're finished

It's also possible to record a new message using the menu on your
phone. Detailed instructions for that can be found in the manual, also
on page 78.

I hope that solves your problem! However, if you need any further
clarification on this answer, please feel free to ask.

Deadlychiapet-ga

Search strategy:
Searched through Panasonic UK's download centre
http://www.panasonic.co.uk/downloadcentre/

abundantly clear, quick, polite