Shabdbhedi Express: गति इसकी शब्दों को भेदती है, पूरब को पूर्वांचल से जोड़ती है - Dr. Abhishek Rai

Some additions and corrections:
Corrections:
Kalka Mail - 1891
Punjab mail (Bombay-Lahore) - 1904 (as a dedicated train) -1890 (as a through train).
Flying Ranee - 1937 (The 1906 date is a popular myth)
Darjeeling...
more...

mail - 1964 (The historical Darjeeling mail was a different train).
Doon express - Earlier than 1925, probably around 1913.
Additions -
Madras-Mangalore mail - 1862
Bangalore - Arakkonam passenger - Started in 1862 as Beypore-Madras express
Madras-Bombay mail - 1870
Bombay - Calcutta mail (via ALD) - 1870
Howrah-Amritsar mail - 1900 (Started as Mughalsarai-Peshawar mail)
Dadar Amritsar express - 1907 (Started as Bombay-Delhi express and later extended to Peshawar)
Madras-Bangalore mail - 1906 (As a dedicated train)
Madras Mysore Intercity express - 1906 (Started as a special train)
Madras-Bombay express (11041/42) - 1921 (started as a passenger)
Toofan express - 1926