I think your main problem is the choice of aircraft. Those VC10s you fly is both old and inefficient, but still costs quite a lot to lease. If you put them on routs close to there max range, and put a few C-class seats on them, they might make money.
How good is there condition? If they are in bad condition (under 70%), that might be the reason why you need to spend huge amounts of money on marketing to not loose you image.
For the routes you are flying, it seems a B727 or B737 would fit better.