Who sets the difficulty of the puzzle and all that? The computers in the network do - when the system was created, rules were agreed, and written into the software. As everyone runs software following those rules, anybody solving easier puzzles or trying to award themselves more bounty for doing so will have their bounty-claiming transaction rejected as invalid. To loosen the rules, a majority of the computers in the system will all need to accept the new rules - so it will require consensus from the community.
I've been thinking more about this. What does it really mean to say a transaction is "accepted" in Bitcoin? I want to pay somebody 10BTC for a piece of computer hardware. So my bitcoin client software looks over my bitcoin addresses, and assembles a transaction stating that I take money from a bunch of previous transactions that send money to my addresses and send 10BTC to one addresses, and the change to a newly-minted address of my own. That's signed by my private keys, to prove I own the addresses the money is coming from, and fired off into the Bitcoin network. Which, in practice, means it's broadcast so the whole world sees it.
Now, anybody seeing that can check it's valid, by looking at the global transaction history to see if the source transactions were valid, and that the transaction is signed to prove that I was the owner of the addresses those transactions paid into, and so on. So the recipient knows I'm sending them the money within a few seconds. However, there's a number of frauds I could be committing, including taking advantage of network delays to spend the same money twice - which won't be detected until the second transaction also arrives at the recipient and they realise they've been duped. So there's more to it than just that.
You can consider money to have "cleared" into your address if, and only if, other recipients will accept you transferring that money to them as valid. So if some of your balance is from a dodgy transaction, and you decide to try and spend it anyway, then the new recipient should reject that.
So to build a global standard of "accepted transaction", we have the bitcoin miners. They all run software that checks the validity of transactions, and assembles groups of accepted transactions, and then invests significant effort into demonstrating that they agree with it. This means that an onlooker can tell that the majority of the miners agree on the validity of a transaction if lots of proof of it accumulates. Currently, the standard is that this involves about an hour's total computation from the majority of the miners in the system. If your transaction has withstood that much scrutiny, then it's considered "baked in", and transactions spending the money you received in that transaction will now be considered valid in turn - in other words, you can now spend the money. The miner's reward for providing this service is that they are allowed, subject to certain constraints, to sneak in their own transactions that let them create money from nothing and give it to themselves; and they also get any transaction fees that were provided with the transactions they accept.
So "validity" all boils down to what transactions more than 50% of the miners will accept. If there was a bug in the software that let a transaction which created money from nothing count as valid, then the miners would accept it as valid and it would be baked into global history. And therefore the senders of those transactions could magic money into existence. Not cool.
But if that bug was found, and a new release of the software rushed out, then that loophole would be closed as soon as more than 50% of the miners ran that software. Indeed, if such a bug were found, many miners would probably stop mining - as contributing to devaluing the economy would reduce the value of the bitcoins they can award themselves for doing the mining - until the patch was in place; bitcoin transactions would just hang in limbo until it was ready.
Nonetheless, it seems that a lot of scrutiny needs to be applied to new versions of the rules miners use to validate transactions in case they have loopholes. As they are the rules of the Bitcoin economy. And a LOT of scrutiny needs to be given to the implementation of those rules, which is where it's really easy to let bugs in.
Changing the Rules
For instance, as there's a cap of about 21 million bitcoin in existence, and each bitcoin can be divided into at most a hundred billion little pieces, there's a constraint that you can never spend an amount smaller than a 21*10^17th of the total value of the economy. When we're a universe-spanning colony of post-singularity time-bending superbeings, that might be an issue.
But it could be fixed. Just create a new currency, within the same bitcoin infrastructure (but with its own transaction types for transacting it). And then create a new kind of transaction which splits N bitcoins into N*2^128 "minicoins", and another which does the reverse. You'd extend the "is this transaction valid?" routine to now accept four kinds of transactions: Traditional bitcoin ones, new minicoin ones, and the two directions of exchange transactions. If everyone agreed that was a good idea, and all the implementations implemented it, and everyone installed the new implementations, then after a while, people would start to find their test transactions attempting to split a bitcoin up would be accepted by the global mining community. At which point, the new change would be "in". The changeover to the new implementation should be done at the same time across all the miners if possible (perhaps at an agreed block number), as otherwise, miners running the new rules before a majority of the mining capacity is would sometimes win blocks that don't get accepted by the majority, losing their bounty (and, therefore, having wasted their time).
A similar process could be followed to change the rules for generation transactions; perhaps the bounty rules might be changed so that the system will no longer cap at 21 million BTC, but grow with the size of the economy or something.
Which is very interesting.
Making the change would require consensus amongst the implementation teams (currently, there's only really one, with Freecoin hopefully soon being another) followed by consensus amongst the miners to install the new implementation.
Compare that to the analogous process for national currencies: governments can choose to print more or less money as they see fit, while a tangled combination of laws and banks generally define the rules for transferring funds. The Bitcoin economy is, largely, defined by the miners and what transactions they choose to accept. They know that if they change their rules to unfairly benefit themselves over non-miners, then they can't stop more people joining up and becoming miners too, dissolving their advantage with more competition; and if they ruin the Bitcoin economy, everyone will start a new one with saner miners, and their mined bitcoins wil become worthless. There's little incentive for an individual miner to accept transactions that other miners wouldn't; because if they win a block with such a transaction in and try to claim the bounty, the others would reject their block due to the bad transaction, and they wouldn't get their bounty accepted. It's in nobody's best interests to vary the rules without gaining a consensus between the implementers first, so any change to the rules will necessarily be rather conservative and careful.
But, the bitcoin economy needs to be careful. Don't let any one miner (or mining pool) get too close to 50% of the hashing capacity. And get more competing implementations of the rules in place. Bugs in the system would hit confidence in the economy hard, even if they were fixed rapidly. (Also, rolling out en emergency bug fix would probably be the easiest way for an attacker to try and slip a new bug in with insufficient review).
And... back to politics
It's not often that you get to see anarcho-capitalism and enlightened self interest having such free reign of expression; and it will be interesting to see how it pans out.
Currently, powerful vested interests (largely, big business) have found ways to lobby governments to do things in ways that benefit them. What will happen if bitcoin becomes a significant proportion of the world economy? There will be cries that we can't let the world be run by a bunch of nerds. Perhaps countries will enact rules that bitcoin miners on their soil have to run approved software, and those countries will form an international committee to decide what rules that approved software should run. Or perhaps private bitcoin mining will be made illegal, and nations will set up their own supercomputers to dominate the mining capacity, with their own rules controlling the money supply. I can see that happening; and then anti-money-laundering rules (transactions above a certain amount need to be signed with an X.509 identity or similar?) will be introduced. But that will, at worst, just cause a fork of the chain, as people who want an unregulated economy will just go off on their own separate way with the old rules.