I may have fixed this inadvertently...
GMail basically do not use IMAP folders like other providers, due to their labelling system I believe. So making Mail.app work with GMail is a bit of a problem, there are many posts about this.
As part of my effort to make Mail work with Gmail I have hidden the All Mail folder in Gmail and then use the Archive feature in Mail.app. This creates another IMAP folder called Archive. So in effect my new Archive folder in Mail (which is a label in GMail) is my new All Mail box with only mail I want in Archive (as opposed to GMail keeping some rubbish emails in its All Mail which I do not want to see).
Anyway, since using this Archive box in Mail and hiding All Mail, I am not longer seeing these duplicate tasks in Omnifocus. The Mail no longer has the old label in GMail when Mail moves it to the new folder.
So maybe the issues was due to GMails IMAP folder setup, and having the All Mail box there, but I cannot know for sure. Maybe its because with All Mail showing the email in Mail will be in All Mail AND in my custom folder than Omnifocus scans. So maybe when Mail moves it, due to the other copy being in All Mail, which is what GMail attaches the label to, it keeps the old label. But without All Mail, my message is only in Mail once, in the folder I put it in. So moving it actually moves it. I dont know though, just a guess!
Spoke too soon, its still got the issue. It just does not do it all the time.
So basically the issue is when using AppleScript to Move a message into another folder (and using GMail IMAP, so Labels in GMail), the original label in GMail is kept even though Mail does not show the mail in this folder. But Applescript still thinks the mail IS in this original folder (i.e. it sees the GMail label assigned to the message, even though the message is not in the Mail folder).
Hope that makes sense.
I think the problem is solved, discussion on another site here:
Needed to select the destination folder the message was moved to to update GMail label and Mail and therefore remove the message from the sourcfe folder in Mail and prevent it from adding to OF again. Full Applescript on the link too.