ive owned both of these boards, and i say, if you must choose between these two, go for the k8n-e deluxe. i am almost certain with a good bios update, it will be a top nforce3 250 performer. the k8v is also a good choice, as a matter of fact (mine is for sale in the f/s trade forum here) but i wouldn't recommend it if you were doing overclocking with the lack of an agp/pci lock.
if you are planning to run stock speeds, i'd say just save yourself the money and get the k8v. it does has the robust features most people need.
as far as memory, i always went with ocz eb series for these boards, but seeing as they discontinued this memory, i say try something that will give you tight timings @ ddr400. perhaps some bh-5 chips since people seem to be selling them, or the new corsair xl's.