On face value, I would suggest that something is making memcached crash. And if memcached isn't running when you try to stop it, it will fail (because it's stopped already). So that would explain why
/etc/init.d/memcached stop (or the first part of
/etc/init.d/memcached restart) is failing.
But then you go on to say that you need to run
killall memcached to get it to stop. That would suggest to me an issue with your init system losing track of the process. As I don't know what init system you are using, it's hard to be sure.
Most distros these days use SystemD and I've had some edge case issues with Debian because of problems caused by the backwards compatibility with the old SysVinit scripts.
Looking at the commands you are using to control your service, you are directly calling the SysVinit script, so I'll assume that either you're using SysVinit, or SystemD with SysVinit compatability.
If you don't have any SystemD, then it's almost certainly something wrong with your initscript and/or memcached config.
If you do have SystemD, then it's likely being caused by some communication issues between your initscript and SystemD (and there could still be memcached config issues too). IMO, the best path forward there, would be to write a proper SystemD service file and use SystemD commands directly; i.e.
systemctl COMMAND SERVICE_NAME.service. They're super easy to write, google will help you out (try something like "how to write systemd service file")