Possible variant: Accept a picture/image of a handwritten message, and apply it (cleanly) to the card / piece to be mailed.

EDIT: I'm thinking of e.g. an image from a cell phone, if you can get sufficient quality. Not something that becomes significant effort for the user. Bonus points if, or necessary that it looks (fairly well) handwritten.