I too am buying my first laptop on a similar budget.
I have looked at many and scoured magazines and the net.
I have plumped for a Toshiba A10 click here as it has fairly good revues. It comes in at £703 inc vat and comes with a USB external floppy drive.
A slightly cheaper option is click here at £545 inc vat but this only has a 20GB hard drive.
I have not found a new machine in this price bracket with 512MB of RAM.
Crucial sell 256MB Ram for these Toshiba models at £28.19 click here