I wouldn't necessarily trust that store bought ice is "sterile" or even sanitary. Why buy that when you can sanitize containers and freeze your own pre-boiled water that you know for sure is sanitary. Palmer even says in his book to be wary of store bought ice. those bags aren't very thick/strong and often have tiny rips in them. So use them at your own risk, I for one won't be doing that any time soon.
A way to save water and cool faster using a coil chiller, is to have two coils attached in series. the water goes through the first one which is in an ice bath and then the second in the wort. Also a whirlpool chiller like the one that Jamil Zainasheff designed would also help greatly.