My guess is when you loaded your previous backup/sync to the new 4S it merged the mail accounts...which happened to me as well, i received duplications also.
I deleted all my mail accts, then created my google gmail exchange again, synced it, backed it up to icloud, and no issues anymore.
the merging doubled the messages