Rather than randomized divisions, something like tiered divisions might work. The team with the best historical record is in the AL West, the second best is in the NL West, third best is in the AL Central, and so on. Then the seventh best team is in the AL West, eighth best is in the NL West, and so on from there. Divisions are still fairly fluid, so you can't predict exactly where you'll go, but it might give teams that usually get sorted to currently difficult divisions like the NL West or AL East more of a chance to succeed.