But, I do not remember the original email ID with which my account was registered 5 years ago. Though, I have provided signed message from an address, that was used within one month of account registration.
What am I supposed to do?
If they are telling you that you require the original email address then you require the original email address. You can send an email back to see if there's any possibility of proving otherwise, but it seems that the prerequisites are pretty strict in account recoveries. Unfortunately, I imagine the majority of people trying to recover their accounts would have lost their original email address especially if it was made a a few years ago.