Hmmmm I know very little (read as: nothing) about steppers and their shields but.... the one thing you didn't mention in the whole explanation of diagnosing a power problem was the power supply.
Did you try different sources of power? Could it be that the common thread across all the combinations of Megas, shields and motors is the same source of power?