A reputable retailer like Electronic Boutique would not sell a used copy of a game as new.
EB - reputable?

Ok seriously, In my own experience with them they've proven themselves as some of the worst offenders (ie. staff/people opening games using serials and resealing)
In any case, you should be taking this up with EB now. Since the devs have verified that your serial has in fact been used before. Print out the emails you have with SD and show them to your "reputable" EB store. If they in fact are reputable they'll do the right thing and exchange it for a new one.
the Monk