> it seems like the East Coast and Midwest are slightly more strict in wanting people to dress business casual, and be clean-shaven

I'm 33, in the Atlanta area, and I've never even heard of a company with a policy against beards. I'd estimate somewhere close to half of the men here under 40 have beards.