Excel Links to files on network not updating

I have over 100 files that are linked together. These
files are located on a network drive that my entire
department has mapped to P. When we open some of the
files and click Yes to update links, the links do not
update. Sometimes the cell will show the link as P:\ and
the path and other times is will show \\HQS400\Shared\ and
the path. If I open (using File/Open) one of the files
that is linked, the links do not always update; however,
if I double click the cell (I have Edit in Cell
deactived), it will open the file regardless of the path
and update the links.

Any ideas on how to ensure that the links get updated
everytime I click Yes to update links rather than by
opening all the files.