Frank, [Should + have + past participle] does not always express what was NOT done. It can also express subjectivity about something that may or may not have happened in the past and act like a subjunctive verb. It is sometimes called the "putative should" and is used mainly in "that" or noun clauses. I was suprised that he should have done it. I am suprised that he should have married an older woman. I did that which I should have done. = I did what I should have done. This is not the same as " I did what was correct." It rather means I did in my opinion what was generally considered to be correct, or what circumstances dictated that I do. This only makes sense if the context is emotional, and casts doubt on the absolute truth of the statement. Otherwise it refers to an event that did not happen as in "I did what I should have done earlier". The verb in the main clause states a fact that contradicts the imaginative [should + have + past participle] clause. It was odd that he should have felt lonely when he was in California. I can't understand why he should have done such a thing.

Modal verbs express of ideas (obligation, permission, ability, necessity) as perceived by the speaker. There is no contradiction in grammatical meaning in the way you described because two people could be in two different situations, use the same modal construction, and be communicating two totally different meanings. Once you get beyond basic mechanics of grammar, you have to loosen your grip on grammar "rules" ... rules are general guides to interpreting the speaker's meaning ... so much depends on context.

"I just did what I should have done" sounds good and sounds better than "Anybody could have done what I did" in this context. or you can say, "I just did what anyone would in this situation"

YOU WROTE: My question is ""should have" is used to express regret or criticism for not having done something or unfulfilled obligations, but "I just did what I should have done" also implies "already fulfilled obligations", which contradicts itself, doesn't it? REPLY: The contradiction comes from the first part being just the words "should have blah blah blah" which means what you said: regret over something not done. In your sentence, you add the contradicting information yourself by adding "I just did" -- by "just doing it", you fulfilled the obligation that you regret (previously) not doing i.e "what I should have done"

I think, you may. I'm not sure this construction complies grammar strictly, but it is is just common in spoken english - Google find 776,000 exemples. (So, your partners will understand you. ;))