For the states I've been curious about in the United States, each state's Secretary of State usually has a search form for corporations, LLCs, and limited partnerships. examples: California (http://kepler.sos.ca.gov/) and Washington (http://www.sos.wa.gov/corps/).
It depends where you are, but many places have something broadly similar. Here in England, for example, any limited company must have a registered address and mail to that address must be read. The registered address must be shown in various places by the company, and can also be checked by anyone through Companies House, which is the government authority that deals with such things. These are all legal requirements here, and the authorities will not look kindly on a company that doesn't follow the rules, with potentially serious implications for its directors.