What is the recommended or best action, when the product owner adds new stories in the middle of a sprint? Debate is accepted and encouraged.

Try to shift the user story into next sprint. If PO is not agreeing for it then estimate and see if it can fit into the Sprint. If it cannot fit then think which low priority user story can be dropped to take the new user story.

The first step is to figure out if the new story is indeed that important and must be realized within the current sprint, since this might effect the current sprint. If the answer is yes, then the next thing to do is to let the team make an estimate as quick as possible. After that the product owner must choose which unstarted stories may be taken out of the sprint.