I've heard of some cars needing batteries sooner in Europe. There were complaints on an overseas Kia forum. These systems do improve the numbers on their tests. So manufacturers could skimp on the system just get a better number for cheap, in theory. Manufacturers in the US will get a credit or something to their CAFE numbers by selling start/stop systems, but they have a small impact on the window sticker numbers.
Ford has been selling their system in the Fusion for over a year now. Which is about how long batteries were lasting in those Kias, and I haven't heard of any complaints with the Fords. If worried you could put a second battery with isolator into your car like GM has done. I think the Malibu has a partial electric AC, and thus higher accessory load than atypical car, though.
The only starter dying early I heard of was the one on Wayne Gerdes Accord. That wasn't an automatic system, and it involved more stop/starts than any of these factory ones would add to a starter. Which is likely a heavier duty to begin with.
One that note, here is some info on Mazda's system.
http://www.cleanmpg.com/forums/showthread.php?t=6226
I believe the official name for it is i-stop now.