I have been having trouble with mintmenu being very slow to start up recently, I went to reinstall it and it said it could not be reinstalled as it was no longer available.
Investigating this further I found that it you look on packages.linuxmint.com it has mintmenu 5.1.6 (which is the one I have installed) but if you look on packages.linuxmint-fr.net (the repo I am using at the moment) it only has mintmenu 4.9.9.
I wondered which is the correct version for LMDE?
I am going to try 4.9.9 again anyway to see if it prevents the long delay at boot up. I will let you know if it makes any difference.