I'm making some guesses here...
1. These executables were built using VS 2005, correct?
I've experienced this problem on two PC's with VS 2005 installed when
attempting to run *some* VC++ applications.
I can make the problem occur by selecting "Rebuild Solution" from the Build
menu.
If I create new solutions and am careful to only use Build... commands,
never Rebuild..., I can import the original source code from the failed
solution and it will run.

2. The PC in question had beta or CTP versions of VS 2005 on it at some time
in the past (even if you uninstalled them), correct?
That seems to be a factor in this issue. You *may* have some success in
searching for multiple instances of the "missing" file and renaming the
older instances, but my experience with this is that it may or may not be
helpful.

I reported this "bug" in the appropriate forums, and also sought advice from
Microsoft reps via my MSDN subscription support, but *nobody* was able to
reproduce the problem, so it must take a rare combination of
circumstances/events (you're the only other person I've seen mention it).

Bottom line: As I had to rebuild one of the PC's (hardware failure) with
this issue, and formatted the HD, then reinstalled the OS (Win XP Pro SP2)
and all apps clean, I'll predict that will fix it.

If my guesses above are wrong, ignore what I've said. Sorry for the bad
news.

Several .net/framework exe files such as....?  Please give specifics - are
you talking about apps that you wrote, or tools that are included with the
.NET framework?

msvcr80.dll is the VC8 (aka VC 2005) runtime DLL.  It's installed as a part
of the .NET framework as the CLR itself depends on this DLL.  If it's not
found, you have a corrupt installation of .NET and/or Visual Studio.
Uninstalling and reinstalling the .NET framework and/or Visual Studio should
correct the situation.  As another respondent mentioned, in the worst case,
you may have to rebuild the PC from the ground up if something's messed up
that prevents .NET from installing correctly, but I'd try quite a few things
before resorting to such a drastic measure.

-cd