That is indeed interesting. We rolled out a fix that hit last Thursday/Friday and fixed issues related to what Bas mentioned. At the moment, Brad, Greg and Andrew are the only reports I have of people still not being able to empty their trash.
Andrew, are you also using Gladinet (or another third party like Memeo) to upload your files/folders? If so, this could indeed be key.
In this case I would highly recommend requesting help from the third party sites since they can use the same API that created the items to delete them.