The Deluxe accepts more SATA devices, has wi-fi, more RAID types, better onboard audio and S/PDIF output, and yes apparently it's easier to overclock. I would probably get the Deluxe, even at $100 more. I read that the P5K overclocks a bit better than the GA-P35, by the way.
I've never used Mushkin RAM but I hear it's good. Lots of people here like SuperTalent or Corsair too. I have OCZ and it's fine. I'll let the experts handle this one.
Edit: how about GA-P35-DS3P, this one has FireWire.