I had the same problem and finally found a solution that worked, and it doesn't involve deleting everything and starting over.
1. Rename all the shortcuts you want to get rid of. (I put three dollar signs in front of each one so they'd be easy to pick out in the list.)
2. Wait about an hour to be sure the change has synced to iCloud, then do the same on any other iOS devices or Macs you have just in case those also have ones that need deleting that weren't caught in Step 1.
3. Now wait a week to be absolutely certain the changes have propagated through all of Apple's servers and what have you.
4. After the week has passed, delete all those renamed shortcuts. Again, wait an hour before you do the same with your remaining Apple devices.
That's it! Those shortcuts should be gone for good.