This update to Emacs 26.1 broke my movemail setup (Buster) in exactly the same way.
The bad thing here is, I don't even have mailutils installed as this package is pretty much bloated. But for some reason I had a movemail executable in /usr/bin/emacs/v25.2/x86_64-linux-gnu and had no problems with mail retrieval from a (file) spool. (Apt-file somewhy doesn't show me the owner of this executable). After upgrade to 26.1, there is no movemail executable in /usr/bin/emacs/v25.2/x86_64-linux-gnu anymore and I cannot retrieve mail from a local spool, observing the "searching for program" error. One <ugly> hack is to retrieve the old movemail executable from a backup or deb package, and reinstate it in /usr/bin/emacs/v26.1/x86_64-linux-gnu. Thanks Oleg
