Giving full rights to the queue to the "Everyone" user didn't work for me. I had to add the "ANONYMOUS LOGIN" user, which gets "Send Message" permission by default. I then restarted the MSMQ windows service. That did the trick for me.

This is in Windows 10 Pro.