Sorry to say but the proposed solution did not help. After I had followed the instructions it did at first not solve the problem. But when I rebooted my comuter the error message did disapear, leading me to believe that it was because of the steps I had taken.
Next time I started my computer it was however back. I tried to follow the steps of the proposed solution and that did not help. I think that it is only logical that it didn't help (I was suprised when it seemed like it did help at first) since the problem described in http://www.winhelponline.com/blog/fix-corrupted-recycle-bin-windows-7-vista/ is about not being able to delete things fro the recycle bin while my problem is that that anoying error message keeps poping up every time I do delete something. The deletion itself works and the files are removed corecctly.
I am also pretty sure that the problem is connected to MyPassport since the error message only appears when MyPassport is connected to my computer. As soon as I remove it everything works fine.