Rummaging through some bags from my old house have unearthed the GNER timetable for weekends 11 sep to 11 dec 2004.
Saturday departures 11/9 to 30/10
Carlisle depart
07:58,08:56,10:01,10:58,12:01,12:59,13:59,15:01,16:01,17:01,18:01,19:00.
arrival at Newcastle 09:30 then xx:30 apart from 11:31,15:32 and 18:33.
Newcastle depart
08:18,09:15,10:28,11:18,12:18,13:18,14:18,15:18,16:18,17:16,18:18,19:24
arriving Carlisle 09:40,10:29,12:01,12:38,13:41,14:33,15:43,16:37,17:34,18:51,19:40 and 20:52
Looking at the above the best journey time was 1h14m to 1h33m depending on the trains in front, allowing plenty of time for early arrival for the eastbound journeys.
If you need any more times ask away.