Gift Message for Subscription Mailing

[historybymail]

We want to be able to offer a personalized gift message option with our gift subscriptions. How can we make it feasible that we allow customers to make personalized messages? All our subscriptions are mailed, not shipped, and there is no tracking on first class mail. We do not want a digital gift note, since people will receive the digital note weeks before the mail arrives and get impatient in the meantime. Since we do not ship, we have no shipping labels to put the gift notes on.