Hmm, this certainly baffles me. What makyo suggested was that your file-system might have been mounted with the -noexec option, as you see, for instance, with the proc file-system (which is normal, for the proc).

But from all the output you have posted, I cannot see anything wrong. The only thing I have seen so far is that, for some reason, it thinks the file does not exist when you try to execute it.

I also see that each directory in the path /usr/local/bin has the executable bit set for every user, so that is not the problem either.

Can you do the following please:

There is a new twist on this:
I tried copying some of the binaries to other directories, like ~/bin, and the system cannot
find them there either.
Something is standing out: it seems like all of the programs that are "not found" are old 32-bit
binaries that I compiled on a 32-bit Linux system with gcc years ago.
Did somebody change something to make the system no longer run 32-bit binaries?

The system is still 64-bit Debian, latest etch release.

And the answer is the same:

bash: ./bladeenc: No such file or directory

== when it is obviously right there.

terry@rebecca:/usr/local/bin$ ls -l bladeenc
-rwxr-xr-x 1 root staff 279056 2004-12-06 10:53 bladeenc

But what if, like I just asked in another post, the system
is now only looking for 64-bit binaries, perhaps discriminating
by something in the header? That bladeenc is an old 32-bit
binary, and so are the others that are not being found.

And like I said, in the other post, copying one of the "not found"
binaries to ~/bin doesn't help or change anything, so it does
not seem to be directory-specific.

A 64 bit system should run 32 bit executables just fine.

On one of your "not found" files, what does the "file" command say?

e.g., "file /path/to/not/found/binary"

It should say something like this:

I finally figured out what the problem was. I was running binaries that were compiled for 32-bit Linux on a 64-bit Linux system.