This has been going on, like most esri bugs, for many years and many 'versions'. Copying a layer, or group of layers (shapefiles, rasters, whatever) in arc map and pasting it and - whola, even if it's in the exact same .mxd project, the file paths are lost and must be fixed.
Sometimes. Sometimes it doesn't happen, sometimes it does; sometimes to all, sometimes less than all.
I've had this experience on many computers over the last decade - Government, NGO, and private, win xp and 7, from versions 9.2 -10, all updates, etc. At the moment I'm using a 1 month old GIS workstation with 48gb ram, many processors at high speed, and w7 and agis version 10 (though I use 9.3 as much as I can on another machine for obvious reasons) and still get the same result - sometimes! - with a single layer or groups. So it seems to be not related to the machine, version, or my other software.
It just happened again - to some, not all of the paths in a copy/paste from one open project to another - and now I have to go back and fix (again!) many links that arcmap, you'd think, would be able to keep track of as they were working when I copied it!
I always use relative paths, but have tried in vain to prevent this, with no luck, in the past using absolute paths.
This is one (of oh so many) bug that I really hate to see continue year after year!