A final thing that i don't understand is how different versions of Bitcoin nodes agree on Fee/Kb. Bitcoin 0.8.0 require 0.0005 btc/kb, Bitcoin 0.8.2 require 0.0001 btc/kb, and recently Bitcoin 0.9.0 requires 0.00001 btc/kb.
They don't agree.
Bitcoin is a voluntary system.
This. To the OP, it helps if you stop thinking about "bitcoin" as this abstract tightly coupled unified network running a single official "standard". In reality it is a very loose protocol made up of hundreds of thousands of independent nodes and at no point in time are all the nodes in agreement on anything.
If I wanted to I could change my node to not relay any transaction unless it has a fee of 0.1 BTC or more. There wouldn't be much point in doing that (tx would just route "around" my node) but I could and so could anyone else. If your tx has a fee of x and priority of y then each individual node acting totally independent of any other node will determine if they will relay it and just because a node relays a transaction doesn't mean that other nodes won't refuse to relay it further based on their own completely independent determination. For any given transaction is is probable that at least one node on the network will refuse to relay it due to double spend, insufficient fee and/or priority, inability to verify, tx not meeting "IsStandard" requirements, outputs below the spam threshold, etc.