Long-run stochastic stability is a precondition for applying steady-state simulation output analysis methods to a discrete-event stochastic system, and is of interest in its own right. We focus on systems whose underlying stochastic process can be represented as a Generalized Semi-Markov Process (GSMP); a wide variety of stochastic systems fall within this framework. A fundamental stability requirement for an irreducible GSMP is that the states be "recurrent" in that the GSMP visits each state infinitely often with probability 1. We study recurrence properties of irreducible GSMPs with finite state space. Our focus is on the "clocks" that govern the occurrence of events, and we consider GSMPs in which zero, one, or at least two simultaneously active events can have clock-setting distributions that are "heavy tailed" in the sense that they have infinite mean. We establish positive recurrence, null recurrence, and, perhaps surprisingly, possible transience of states for these respective regimes. The transience result stands in strong contrast to Markovian or semi-Markovian GSMPs, where irreducibility and finiteness of the state space guarantee positive recurrence.