Each node works independently. Any node running v0.9 will relay tx with only a fee of 0.01 mBTC per KB (vs 0.1mBTC per KB for v0.8.6). The network will have nodes on different versions but once a significant majority is running v0.9 or later will become reliable to relay tx with a fee that low.
Of course miners are free to set whatever fee requirements they see fit (even larger than 0.1 mBTC if they want) so being relayed is no guarantee the tx will be included in the next block.
Thanks for the relevant and helpful reply.
Apparently for the near future one has to continue including a 0.1 mBTC fee per kb in transactions. How long until at least half the nodes run v0.9, do you think?