These are scans from the 1957 NER timetable. I do not have exact answers for some of your questions, but to the best of my knowledge:
65/67 express trains - One of these two trains was later renumbered as 11/12, more famously known as the Lalquila express, which was discontinued recently.
Halts for the Deluxe (Poorva) - This is just an abstract timetable, not the full one. As I mentioned earlier, this was the NER timetable. So, for the lines from other zones, only the timings at some major stations are shown....
more...

I believe the Air-conditioned express did stop at other stations, but they are not shown here.
Introduction of Poorva via Patna - The first Air-conditioned express between Howrah and Delhi was introduced as a bi-weekly via Gaya,Mirzapur on Ocotber 2nd, 1956 numbered 81/82, and is the present day 12381/82 Poorva via Gaya.
The Air-conditioned express via Patna started operations as a weekly train numbered 103/104 from April 1st, 1967 and was converted to a bi-weekly from August 1st, 1971. This is the present day 12303/04.

The Air-conditioned express via Gaya was diverted via Varanasi sometime before 1971.