A building will send out a labor seeker approximately once every month. If four consecutive trips fail to find housing, then it's status will switch to "no workers live nearby". The "warning: poor access to labor" message appears after any failed trip. If a building is in a location where it only find workers on every other recruiting trip, it will always be operational, but it will show the "poor access" message about half the time.
That's the most usual situation -- a building will also immediately show the "poor access" message if its seeker has only found housing in the extended portion of a "long-walk" (check the forum search engine for "wacky walkers" if that term needs explanation ). In that case, labor access may only last for a moment or two -- long enough for a firehouse or a hunting lodge to generate sprites, but not long enough for any meaningful production to occur.