I'm making a shawl like that now - its my second one. My pattern is k3, yo, knit the rest of the row, turn. k3, yo, knit the rest of the row. The holes look fine on both sides.
Are you doing a yarn over at the beginning AND the end of each row? Maybe that is where the problem is.