Hi Gappe,
Have you thought of the Content Organiser feature in SP2010 or an Information Management Policy instead of the workflow? Possibly something to look into for a more robust and scalable solution..
Regarding the issue at hand:
It does seem like a permissions issue. The easiest solution would be to use an impersonation step in your workflow that contains the move operation.
When using an impersonation step, the actions within it run under the context of the workflow author.
If you want to correct it with permissions, can you first please list what permissions you have set for the library where forms are being deleted from?