Coinstar reported a gross profit of $150.58 million for 2005. About 45% of their revenue came from the coin counting kiosks.
Their SEC filings
indicate that they have about 13,000 coing counting machines installed, in addition to nearly 300,000 "entertainment services machines", which they describe as "skill-crane machines, bulk vending machines, and kiddie rides." Roughly 27 percent of their income comes from machines installed at Wal Mart and another 11 percent from machines at Kroger.
The conclusion I draw from perusing the report is that it's a volume business. The OP is right that they don't make much money per transaction, but they profit from having so many transactions that the aggregate is worthwhile. it's an interesting insight, particularly in light of the recent thread
wondered if his mom could have a lucrative business owning a vending machine or two...