@Vero Yup, I have Optimized Storage disabled.
Removing the workflow when the syncing directory was set to ~/Alfred/ worked.
Here are the exact steps I did:
Switch syncing directory to ~/Alfred/
Delete alfredpreferences from iCloud directory
Add workflow from Alfred Gallery
Remove workflow
Close and reopen Alfred preference, workflow is gone
Install workflow again
Switch syncing directory back to iCloud directory
Remove workflow
Close and reopen Alfred preference, workflow still exists
Attempt to remove workflow again
Close and reopen Alfred preference, workflow still exists
So it consistently doesn't persist the workflow removal action when the syncing directory is set to an iCloud folder.