I have seen related problems dicussed here, but not this exact one. When I try to compose a new message in Versamail (using Treo 650/Sprint), I get the following error when entering the email address using the keypad into the "to" field:

"There is not enough memory to perform this task!"

I can enter an address using the "lookup" option.

I have no problems recieving or viewing emails.