Is the mailing list internal or using an external provider like MailChimp or Constant Contact? If you're giving the user access to an external provider's form that will work but it may also allow them to work around it (for example if they want to share it with their friends).
The most secure way would be to use an API call/period import (for external services) or direct update (for internal mailings) using a conditional action or module that's triggered by completed orders.
Edit for further details: Mailchimp does indeed have an API - http://apidocs.mailchimp.com/ - and a Drupal module at http://drupal.org/project/mailchimp so the current functionality is half-way there. I would go the last step and create a custom module that adds subscribers to Mailchimp when they complete their order. At that point it's still a one-time thing, so for bonus points on recurring payments you could keep track of the subscribers and remove them from Mailchimp using the API if they stop paying.
It would take a little coding but it's a realistic setup. I can't see anything you can do without any coding unless the Mailchimp module allows you to set up a page that can then be limited to the role of users who paid (and then you still have an extra manual step).