I know non-profit association accounts for things like bowling leagues, alumni, etc are eligible to have NOW accounts. My question is, do they have to be registered with the state to be considered officially non-profit before they are eligible for a NOW account? Or can we justify them being considered non-profit by nature of the association's activities?

"do they have to be registered with the state"

Well, to put it mildly, typically if a business entity is not registered with the State, they do not exist except in some figment of someone's imagination.

See § 204.130 Eligibility for NOW accounts includes "Organizations described in section 501(c)(3) through (13), and (19) of the Internal Revenue Code" The examples you've cited fit 501(c)7 - Social and Recreational clubs. IF they are organized properly according to the laws of your state, and if they recieved tax exempt status with the IRS as 501(c)7s, then they could be eligible for a NOW account.