I know that during the fall season, the discarded fate cards are shuffled back into the main deck, but what happens if the fate deck empties before the fall? Do they just get reshuffled when the last fate card is drawn or are player just unable to do tasks that require a fate card until the next fall season?

They get reshuffled. It's on page 31 under component limmitations.

"If a deck of cards runs out, players should shuffle the deck's discard pile to create a new deck."