Rule 2-7-2 "The lines are part of the batter's box."
Rule 7-3-2 "A batter is out when he hits the ball fair or foul while either foot is touching the ground completely outside the lines of the batter's box or touching home plate."
The umpire was right that unless ALL of the foot is outside the lines, there is no infraction.
The batters on the other team were following the first rule mentioned here, and were not breaking the second rule. It's just good coaching.
You can counter it by teaching pitchers to pitch to both halves of the plate. If your pitchers don't throw hard enough to jam players who are that close to the plate...you'll lose
Also, in regards to being hit by the pitch, the batters that close to the plate do run the risk of being hit by a pitch that's a strike, which will then still be called a strike without them getting 1st base.