Hmm OK All setting as you described above. I tried this on a new document created in Word 2013 and it works as you described (although the red line is still changed to grey, I could live with that).

But when I try the same settings on an existing document created in Word 2007 I get results as I originally described in my first post. (Deleted text still shows up unless I accept the change which removes the left border marking).

On the track changes options I have everything unticked apart from insertions and deletions. Advanced options is set only to show Left border red lines, everything else unticked.