In playthrough 1, do everything, to level as high as poss as quick as poss, in order to be able to complete the story quests which are hard levelled (have set levels).
In playthrough 2, do ONLY the story quests, as it is the one and only time the quests will be reset. Once you complete the story the second time, you are in PT2.5, everything is in super hard mode (a level or 2 above level cap), that is the time to go back and do all the side quests in order to get rewards levelled as high as they can be. This is also probably the best time to use a golden key or 2.