After losing to hax in the early-30s multiple times, I changed my team around and finally made it to 49 wins in Super Single Train and got my trophy. I was originally running a balanced team, but after changing it to Sandstorm, I'm never looking back. I used:
Brave Tyranitar @ Leftovers
Crunch / Stone Edge / Flamethrower / SR
Adamant Excadrill @ Focus Sash <--(key)
EQ / Rock Slide / X-Scissor / Swords Dance
Naive Landorus @ Choice Band
EQ / Rock Slide / Grass Knot (for Cursers) / U-Turn
The major problem is 356 | Mamoswine set with EQ & Ice Shard... which I can only defeat if TTar and Exca are at full HP, so Tar can take the EQ, hit back, and then have Excadrill finish it.
Gliscor, Donphan, Hippowdon, <insert Def-EVd Ground/Fighting-type here> are also annoying to Sandstorm, but I found Banded, Sand Force, STAB-boosted EQs from Landorus can punch through just about anything. Landorus is also a great switch from TTar since the AI loves to throw EQs and Focus Blasts his way (which never miss, of course).