It's happened to me--single entry visa, the officials at the destination country decided the whole group of us weren't getting in. (Internal issues, not a problem with us.) I think the border guards of the country we left were used to the situation, we had no trouble getting back in as if we had never left. I don't have that passport anymore to see if they put any special notation in it when this happened.
Edit: As per request: This was on the Burundi/Congo border, 1982.