I'm not sure that purchasing a used version is even legal, unless the seller is completely transferring his/her license (i.e., isn't selling you a serial number they already used to upgrade with). Older versions are available unused though. Check Amazon, local retailers and craigslist or eBay (be cautious with those last two, especially eBay).
Adobe has recently announced a subscription edition of Photoshop CS5 Extended, though, which at $35/month for a year's subscription comes to $420 -- about what you'd expect to pay for a legitimate copy of CS4. Month-to-month, it's $49. If you intend to make money with the software, it's a good investment.
If you're just starting out, and aren't planning to use the program professionally, consider Elements. It's astoundingly powerful, and is a great way to get into Photoshop without laying out a lot of cash for stuff you won't need.