In[18]:= AbsoluteTiming @ 
 Solve[(s 1000 + e 100 + n 10 + d) + (m 1000 + o 100 + r 10 + 
       e) == (m 10000 + o 1000 + n 100 + e 10 + y )
   && (And @@ Thread[(0 <= # <= 9 &)[{s, e, n, d, m, o, r, y}]])
   && m > 0
   && (And @@ (((#1 != #2) &) @@ # & /@ 
       Subsets[{s, e, n, d, m, o, r, y}, {2}]))
  , {s, e, n, d, m, o, r, y}, Integers]

Out[18]= {0.940472, {{s -> 9, e -> 5, n -> 6, d -> 7, m -> 1, o -> 0, 
   r -> 8, y -> 2}}}

Removing "m > 0" (which is part of the original formulation) causes the solver to wander around the space of solutions without finishing (probably the space is too large?)

I have the impression that the code provided by the OP is not correct.

I wanted to get your attention so I could point out that MiniZinc, which is free (using Gecode as the underlying solver), solves this problem, with an alldifferent constraint, in about 40 mSec. I didn't know that last time I asked the question.