airhog is right...
It's probably possible to build a system that can run AH well, but your idea of "maxed out" might not work.
And that windows license... An OEM license for win7 home premium will run you $130ish, more than 25% of your budget. WinXP may be cheaper but you'll upgrade eventually, so you might want to get the upgrade up front.
Woot.com, overstock, and other online closeout sellers often have fairly basic refurb systems on sale for around $500. The biggest problem you will get with those systems is that the video card might suck, and it's not always easy to determine if the vid card can be upgraded in the future.
You can build a nice AH system for $500 including the operating system, but I think running AH "maxed out" is a bit beyond $500. Not too far above $500, but I'd guesstimate $700 would do the trick if you got a really cheap hard drive, case, only 2gb ram, etc. You can't skimp too bad on the cpu, motherboard, and vid card if you want to max out the game settings.