Your last point is not true. If you package locally and move the entire folder to another drive the links will be fine.
As for the problem itself, that sounds like either a permissions issue or a bad server connection.
I can confirm that I have experienced problems with files containing"special" characters, like umlaut-characters or accented characters (ü, é, etc), when transferring the files from Windows to OSX. But this did not influence the packaging feature.
I would suggest that file access time-outs are not adapted for the mass of data InDesign wants to collect.
Will give this another try. I'm sure it's not down to permissions as we've elevated access to all the folders and still get the problem.
I think it's more likely to do with the connection over the WAN, just wondering if anyone else has experienced this when trying to package over the WAN and what could be done as a work around.