Quote:
Totally depends on what type of soil you have, how compacted it is, etc. I have a 10x20 shed on solid concrete blocks on a 6" gravel base. I store 3+ tons of hay in there each spring, as well as other miscellaneous feed and supplies, and so far no issues with the footings (4 years since installation). However, my dirt is relatively compacted and becomes a solid rock ledge <2' down. If you're somewhere where your ground gets swampy on a regular basis, it could be a different story.
The one thing I would say, if you use rectangular concrete blocks, just make sure they're the solid ones and not the ones with holes in the middle, the ones with holes can degrade over time and may collapse on you. The decking blocks you mentioned are nice and solid, so no worries there.
Also, good point by Rooneytune, you need to check your local codes to see if sinking concrete piers will require a permit. Our codes are anything 200 sq ft or less, and 10' tall = no permit, there are no foundation restrictions (or overhang limitations, one of my sheds has a nice 4' overhang off the back), but not every place is that relaxed.