I know this might sound very strange, but I have a 2003 Xterra SE SC and it had the exact same problems you are having.... After several weeks in and out of the shop only to be told nothing is wrong because it didn't happen all the time and the shop could never get it to lose power I figured out that there was a problem with my gass cap... new gass cap problem solved... strange I know, but it worked...