Am I understanding the mechanism for transactions properly or is it possible for someone who knows what they are doing and has a lot of computer power to spare (say the US Govt..) to build a mostly complete database of all transactions?
No supercomputer is needed. I've already done it:http://blockexplorer.com/
How hard would it be to scour the net for these and match them up to the public keys we have so conveniently handed over?
Pretty easy to get a list of addresses<->people. Then by following transactions you can get many more addresses owned by the same person. It's harder to see how they got coins, or how they spent them, because Bitcoin tries to mix coins around to some degree. Certainly not impossible, though.
I wonder if perhaps some Chaum-ian blinding scheme might be in order - thoughts?
How do you do this in a decentralized way?