Just so that there is an alternative to DumbCoder's very practical and useful answer, if you find the fights from Bhubaneswar to be way too expensive or infrequent, you could actually travel to Kolkata which has a much better connection to Delhi and many other international destinations. In case if your international travel from Delhi is flexible and you can switch, there could be a very valid alternate directly from Kolkata.
Trains to Kolkata are less frequent, however the flights are much more frequent and since you mention morning hours, there is a train at 08:20 in the morning from Sambalpur reaching Howrah (the railway station in Kolkata) at around 7 in the night and there is a flight at 8 35 in the night reaching Delhi by night 11:15. The train I mentioned has a fairly good (reaching within 20 minutes of scheduled time) time record.
Also to validate Rome2Rio, this specific instance travelling to Ranchi by an early morning (04 30 am) train and taking a close connection in an hour from Ranchi airport or the late evening flight to Delhi is the quickest/cheapest possible options respectively.
Two other suggestions the official site to check train running delays is http://trainenquiry.com and the modern site is very useful when viewing it from a smartphone. I use http://erail.in to check availability (this requires a plugin which may not be useful to you) but generally very quick in retrieving reservation availability across classes and dates.
I also think trains may not be reliable always, but there are few trains which are notorious for their delays, barring which services are generally fine (reaching most destinations within 30 minutes of scheduled time). You can identify those troublesome trains using http://trainenquiry.com