I gave this a try and didn't see the problem. What may be happening with the Shift:=xlToLeft command, is the cells from the Right are moving over to fill the deleted range. If these cells have the same formatting as those deleted it will give the appearance of the format not being deleted. Border in this case.
If you want to delete the contents and formatting try this.