HMm...i've never heard of Asus P4P800 having 3 dimm slots????
Since 865 chipset is dual-channel, there should be 4 slots for memory. You should definately double-check that. Maybe you didn't look carefully or named the wrong board.
As far as RaM goes, I think this depends on how often you upgrade. If you wont' be upgrading for another 2 years, i'd just get 2x256 sticks. Since in the future AMD might also switch to DDRII, making your DDRI ram obsolete. Then why spend extra money on DDRI ram now when you probably won't reuse it in 2 years. Also, if a game will require more than 1 gig to run smoothly, chances are your whole computer will become too slow for it (means videocard and cpu are too slow). I think 1 gig should last you for 2 years easily since even with Doom 3 (the most intensive game), going from 512 to 1 gig produces only slight imporements.
If you plan on upgrading sooner, then if you get 2x512 sticks now, you could simlpy reuse them in the new system.
EDIT: If you do photoshop or seriously intense memory apps, the more the better. If you game and upgrading this system for gaming purposes, forget getting extra 512mb of ram right now since it seems your videocard is only 4200. Put everything towards your videocard if you are a gamer.