Beware, a lot of GDPR quotes ahead.
Do we need a user's consent when being contacted by a contact form?
No, Article 4(11) states:
‘consent’ of the data subject means any freely given, specific, informed and unambiguous indication of the data subject's wishes by which he or she, by a statement or by a clear affirmative action, signifies agreement to the processing of personal data relating to him or her;
If the user knows that he is using a contact form then clicking "submit" is a clear affirmative action.
the user sends you a direct email (without using contact form) with a bunch of his personal data (which you, as a business, did not ask from the user)
The user is the original controller of its own data. When he sends you data for which you haven't beforehand determined purposes and means of processing, then you're not a controller of that data, see Article 4(7):
‘controller’ means the natural or legal person, public authority, agency or other body which, alone or jointly with others, determines the purposes and means of the processing of personal data; where the purposes and means of such processing are determined by Union or Member State law, the controller or the specific criteria for its nomination may be provided for by Union or Member State law;
You are not a processor either because you didn't ask about that data, there is no legal agreement between you and the controller, you're not acting legally "in his name". Article 4(8):
‘processor’ means a natural or legal person, public authority, agency or other body which processes personal data on behalf of the controller;
You are a so-called 'third party', Article 4(10):
‘third party’ means a natural or legal person, public authority, agency or body other than the data subject, controller, processor and persons who, under the direct authority of the controller or processor, are authorised to process personal data;
Which also makes you a 'recipient', Article 4(9):
‘recipient’ means a natural or legal person, public authority, agency or another body, to which the personal data are disclosed, whether a third party or not.
Now, as a third party you can process data without the data subject's consent for your legitimate interests. Article 6:
Processing shall be lawful only if and to the extent that at least one of the following applies: (...) processing is necessary for the purposes of the legitimate interests pursued by the controller or by a third party, except where such interests are overridden by the interests or fundamental rights and freedoms of the data subject which require protection of personal data, in particular where the data subject is a child.
Which means that you can delete unwanted data (you have a legitimate interest to do not waste your server space with data you are not properly authorized to have) or even call the police (eg. someone sent you child pornography). However, you should inform data subject(s) of all things listed in Article 13 even if you're not a controller and describe your "legitimate interest" as there is a special rule in Article 13.1.(d):
Where personal data relating to a data subject are collected from the data subject, the controller shall, at the time when personal data are obtained, provide the data subject with all of the following information: (...) (d) where the processing is based on point (f) of Article 6(1), the legitimate interests pursued by the controller or by a third party;
Your next question:
If the answer to the first question is "YES", that how do we manage the consents?
You have to manage them somehow even if the answer is "NO".
So, do we store each and every email in a database?
You email server IS a kind of database already. You should try to do anything in it. It's probably very secure (unless you use weak passwords) and has all search and filter functionalities you need.
UPDATE with some historical perspective:
To further justify my statement, I will recall the predecessor of GDPR, the Directive 95/46/EC which states in Recital 47:
(47) Whereas where a message containing personal data is transmitted by means of a telecommunications or electronic mail service, the sole purpose of which is the transmission of such messages, the controller in respect of the personal data contained in the message will normally be considered to be the person from whom the message originates, rather than the person offering the transmission services; whereas, nevertheless, those offering such services will normally be considered controllers in respect of the processing of the additional personal data necessary for the operation of the service;
So once again: if someone sent you some data via e-mail or web form, he/she was considered the controller.