If two parties agree to the terms of an exchange, then there exists an enforceable contract. A signature is not needed to create a contractA signature is not needed to create a contract.
However, an intent to negotiate a contract is not, per se, a contract. Absent some specific and explicit measures (which for major deals may be codified in an MOU or LOI that itself contains contractual terms), if you can't reach an agreement on terms then there is no contract.
It's up to the particulars of "the verbal agreement to start the hiring process" whether an agreement on exchange has been reached, or merely proposed. E.g., "You and I agree that I will pay you $X in exchange for Y due Z" is a contract.
"You and I agree that we'd like to work together, and we'll hammer out the terms X, Y, and Z by the end of the week" is merely a proposal to contract, not an actual contract. Of course, this doesn't mean you're immune to liability for failing to reach a contract in this hypothetical: you can always be sued!