You yourself can not delete the destiny quest.
First question: Did you check your entire quest journal? Every singel quest? From what you said your last step should have been getting the phoenix of the east, after which your trainer should have send you to Croms Rock in Lacheish Plains. You should find the quest under: Cimmeria - Lacheish Plains.
If you have already been to Croms Rock, the quest should be under Aquelonia, King Conans Castle now.