It seems hard to do it directly, but I've been analysing [1] for an upcoming project, and they do some clever tricks to amortize the cost. If you get to try it out, let me know what you think!

[1] http://dev.blockcypher.com/#microtransaction-api