Tom, it sounds like you may have a faulty LCD chip. If the LCD works fine for a while, and then parts of the letters start disappearing without changing the data to the LCD then it seems unlikely to be a problem with the interface or Arduino.
Take a picture of the LCD display showing that parts of the character display are missing and bring it in to Maplin's and ask for a replacement.
FWIW, Maplin have significantly raised their prices on all components over the last few years and you can usually find the same item or better new on ebay for half the price. For example I bought the 16x2 blue backlit module here
, it cost £5.50 shipped and I received it in the next mornings post.