I am not sure that I can use only present simple in this case.
I should have taken my umbrella before I go/went - present simple or past
The keys must have fallen out of my pocket before I get/got in the the the car
The verb tense of the subject should be consistent with the verb tense of the dependent clause.
Thus, the correct sentence from your first example is:
I should have taken my umbrella before I went.
'should have taken' - past tense
'before I go' - present tense
'before I went' - past tense
Think of it this way: If you 'should have done' something in the past, you cannot simultaneously 'should have done' it in the present. You cannot be in two places at the same time.