That's true. You're a free agent until you sign. That goes both ways: the residency can hire another person. However, either of you changing your mind is considered bad form once a verbal agreement has been made.
I recommend you contact the Program Coordinator/Secretary where you scrambled and ask to be given a contract.