While I would agree about not using The Trainline.com directly, because they charge CC and booking fees, it's also best not to rely fully on the excellent NationalExpressEastCoast booking engine. I've noticed that it often won't display the lowest Advance tickets with some companies - I'm not sure why this would be.

Once you know the operator of the train that you want, visit that company's website directly. Sometimes they have extra offers (for example, First Great Western recently had a flat £5 reduction on any ticket --- which turned out to be valid on almost any UK train ---) which aren't as widely advertised.