In many cases people are also willing to opt-in on a list if you offer them a free voucher, toaster, airtime, etc.
A good example is the free airtime offered on Colgate toothpaste recently. The Terms and Conditions can be found online at http://www.colgatesa.mobi/terms-conditions. One clause states, "By entering this competition you authorise the organiser and/or the promoter, to collect, store and use (not share) personal information of entrants for communication or statistical purposes." This is an excellent example of how to implement a legitimate opt-in list.
The communication becomes a problem, when there are no legitimate channels to opt-out at a later stage (after previously opting-in) or you get a call from a call-center or SMS on your new cellphone number that you have not given out to anyone other than friends and family.