Question 1) Am I uninfected? I'm very wary that I might have had some backdoor/keylogger type of infection installed alongside the scareware.
I'll answer this in two parts, the second part first. The way that this works is that both professionals, that would those that work for anti-malware companies, and amateurs, that would be those that don't, get hold of the droppers for these infections and infection test machines in order to understand what they do and how they do it. Following on from that is whether or not it is possible to undo this and also whether or not it is worth the time/effort to do so rather than to reformat and reinstall.
As far as i'm aware this particular infection doesn't create a backdoor or drop a keylogger that would necessitate a nuke and pave, and if it was quicker/better to reformat then I would mentioned this in my original post. I can't say from personal experience as I don't generally go in for the installation end of the malware removal game, but if there was a known risk I would expect that it would have been posted online in an area that I would have access to.
The answer to the first part is probably. As I understand it the warning/threatening screen is pretty much the whole of the infection, so if you don't see it, then you're clean. There may be traces left on your PC, but as they would be inactive they don't pose any risks.
Question 2) Do you think I'm safe to re-connect the machine to the internet? Use it as normal? Log in to password protected sites and online banking?
See above, really.
Question 3) Do we need to continue with xPud and Query.exe anyway?
I would like you to do so to satisfy my curiosity, but it's probably not necessary from your point of view - your choice entirely then.
Question 4) Should I be planning a Windows re-install once I've backed up my docs, photos, iTunes library etc?
I'm sort of feeling that if the machine is actually now uninfected then I don't know if I feel I can trust it without a rebuild...
This is one of those situations where you have to decide what is important to you. It's rather like asking "Should I look under the bed for trolls before I go to sleep?". I doubt that there are any there, so it's a waste of time from that point or view, but if you are going to lay awake all night worrying about it, just look and get it over with.
On the one hand is the time taken to carry out the reinstall, on the other is the peace of mind and also the speed boost that you are likely to get. I see from one of your logs that the Windows install date was: 12/04/2011 20:38:50. Twelve months is likely, in my experience, to have seen a slowdown in your PC due to installations, uninstallations and general PC usage and it is likely that you'll see an increase in performance as a result.
I have to say in all honesty that as I like to wipe my PC every six months to keep it fresh and responsive that in your situation I would probably take the opportunity to reinstall, but this would be on performance grounds rather than in response to the infection. So, you pays your money and you takes your choice as it were. Oh, and given that you have F.E.A.R.: Perseus Mandate installed which is by far and away the worst F.E.A.R. game that they ever released, or more likely that escaped as it really is pants, it would be a service to gamers to see the back of that!
If you have any questions about the above, or anything else, please ask. I don't guarantee to post useful answers, but you can probably expect a smile at least from them.