I've solved this for myself.
The folder name that holds the spam has an asterisk in it. I renamed the folder without the * , and recreated the deletion policy. It ran fine last night. I can only assume that the server treats the * as a wildcard (although it still should have matched...).
Hope this helps someone else.