I would start looking for a used IBM or Toshiba machine. See if there are any stores where you can get used computers locally. Or perhaps you know somebody that works at a company that is selling off used equiptment. DONT BUY NEW!! The quality of machines at that pricepoint is a bit iffy in my experience.
As a pointer: I paid 100 bucks for my dads "new laptop". A friend who is Systems Admin at an engineering company got me a no name machine with Celeron 1GHz, 128 RAM and 10GB HDD. So if you look around and have a little luck you could get a pretty nice name brand machine for your 800$.