Update:
Well I finally broke out the airspade today. It has officially been reclassified as an air knife. This thing is bad. I rented a 375 cfm compressor, and promptly blasted a 12" deep, 200' trench in about 15 seconds.
It really only took me about 20 minutes total, and it was cutting through hard compacted clay and roots on a site where they cut the timber with a feller buncher and skidder. I'm real happy with the way it turned out, and I never did find any of the buried utilities. It didn't seem to hurt any tree roots either, but I'd want to cut the pressure back if I had to excavate someone's prize japanese red maple.
The air at the nozzle looked blue, like a propane flame. It got pretty hot, even with heavy gloves, and was pretty loud even with my ear muffs on.
I know how I'm blowing the leaves off the lawn this fall.