I've managed to recover my lost messages. I was poking about in ~/Library/Mail/POP-user@domain/INBOX.mbox and noticed that I had a 127 megabyte mbox there. I backed up this file and then quit Mail. The file shrunk down to a few hundred kilobytes. It looks like Mail.app doesn't actually delete the files until you quit, which is lucky. Wiping the contents of the table_of_contents file and copying over my mbox backup restored my old messages. Phew!
I've learnt an important lesson about making proper backups. I'm going to have to get my Linux box working again. I swapped the motherboard for an Intel brand one which (fingers crossed) I hopefully can get Linux to boot on.
As an aside, my iBook has a record breaking 24 day uptime. Not bad for a notebook (that doesn't stay plugged in).