Suppose

In[1]:= Reduce[{a + b == r, b + c == s, a + c == t}, {a, b, c}]

Out[1]= a == r/2 - s/2 + t/2 && b == r/2 + s/2 - t/2 && c == -(r/2) + s/2 + t/2

That result is simple enough that you can manually check that it will always be correct.

Now substitute in your constants.

In[2]:= p = 29;
m = 2 p + 1;
a == r/2 - s/2 + t/2 && b == r/2 + s/2 - t/2 && c == -(r/2) + s/2 + t/2 /. {r->m^p, s->(m+1)^p, t->(m+2)^p}

Out[4]= a == 2264609839938656962253544726423958389329925477265740 && 
 b == -1485905798391455475132628838090737282072934421601 && 
 c == 3686051234477280753804732628838090737282072934421601

It appears beginning at p=29 and at least up to 100 that b will be negative and this violates your condition that all solutions be positive.

Thus it appears there is no problem with Solve demonstrated thus far by this example.

The reason b goes negative is that it is the only item with a -t/2 and t > s > r. You might ponder why it waits until 29 for this to happen.