Some space can be reserved in blocks for transactions from node runners.
This can be enforced by requiring transactions in the reserved area to have proof of node.
Proof of node can be a scrypt-like system (look up entry corresponding to transaction hash, hash this with the transaction hash, look up entry corresponding to this hash, repeat, chech final hash against difficulty (should be hard enough to prevent spam, but not enough to tie up nodes)) over the block-chain, that requires having the entire block-chain to preform, but can be checked quite easily (about as hard as checking for double-spends on inputs). This would provide an incentive for businesses that want many transactions confirmed quickly with less fees to run a node.