I can make but a few comments.
A31 wrote:I'd like to be able to comfortably run Windows XP Pro or maybe even Windows Vista on it (probably leaning over more towards XP at this point in time), so ideally have 512MB + RAM
I'd suggest 1GB for XP to be really comfortable (even more if you like to have many apps open simultaneously or run memory hoggers like Google Chrome), but generally 1GB should be quite fine.
A31 wrote: 1.6GHz + CPU (Pentium 4 or Centrino or even a Core 2 Duo I don't really mind)
Believe me, you DO mind.

There is a huge difference clock-for-clock between a Pentium 4 and a Pentium M (what you somewhat incorrectly refer to as Centrino). Between Pentium M and the Core(2)Duos, the difference is smaller when it comes to single-threaded applications, but of course in multi-threaded applications, the dual cores shine.
A31 wrote: I have looked on eBay at ThinkPads (namely R40, T42, X31, R51) and it seems like they are all about the same price, around abouts £100, some cheaper, some more expensive
Given the price range and the modest requirements, your best bet is to look at the Pentium M generation of machines, which is any T4x/R5x machine, X31/X32 or even Z60 series (these are somewhat newer and may be more pricey). No reason to go for older systems - the price will not be much lower (how low can it really go), and the bang for the buck surely will be less, especially considering the fact that older machines likely have less life left in them.
Most of these models have some characteristic flaws (GPU/Southbridge failures), so you will never be quite safe, but then again, there is always a risk with an old machine. You may somewhat diminish the risk of failures by going with models that have integrated GPU (R50e, R51e, some of the R51, or the X series), or by going with the newer T43/Z60 series.
A31 wrote:One thing I will add is that I bought a 1GB DDR SODIMM RAM stick for my A31 which I think I kept before I threw the machine out about a year ago, so any other ThinkPad that supports the same RAM as the A31 does would be great as I could easily add 1GB of RAM which would help speed things up a bit
In which case, you want the models that take DDR (not DDR2), which means everything on my list except T43, R51e, R52 and Z60. But then again, if you get any of the aforementioned models already with 1.5 or 2 GB of RAM at a good price, the extra memory stick you have would not make a crucial difference anyway.