Another Emacs TRAMP problem, another solution

The problem

This is documented for posterity because it’s not the first time this has happend to me. The symptom of this problem happened to me when trying to access a remote system, any remote system, through a method like ssh or sftp.
Whenever I tried to access a remote system, I would get an error from TRAMP saying that it can’t find a working /bin/ls, despite the file being obviously in its right place.
The precise error message is the following:

Tramp: Found remote shell prompt on `vattu'
Omitting...
(Nothing to omit)
File error: Couldn't find a proper `ls' command
tramp-get-ls-command: Couldn't find a proper `ls' command

Once you find out that /bin/ls is actually there, there is little left to do but try to see what is wrong with TRAMP. TRAMP is a fickle library and getting it to work might require serious configuration in some case. You can make TRAMP more verbose by setting the tramp-verbose to a 5 or 6, instead of the default.
Once tramp-verbose is set, an Emacs buffer will contain a lot of informations.

20:57:11 tramp-send-command (6) # while read d; do if [...]<<'EOF'
/bin
/usr/bin
/usr/sbin
/usr/local/bin
EOF
20:57:11 tramp-wait-for-regexp (6) #
^M
///fec710f011d52e3acebe364b9088c96e^M
20:57:11 tramp-get-ls-command (1) # File error: Couldn't find a proper `ls' command

What is string there is the presence of the dreaded ^M character. It took me some time to realize that TRAMP may have been trying to look for /bin/ls^M.
The offending option in my configuration was (setq inhibit-eol-conversion 't) which I set to deal with files which may have mixed newline characters. Unsetting this option made TRAMP work just fine.

Reproducing the problem

I had troubles reproducing this problem in order to write this article because TRAMP actually caches the information it obtains from the remote system it connects to. I needed to erase the file $HOME/.emacs.d/tramp and restart Emacs. Once this was done, and inhibit-eol-conversion set, the problem happened again.