We are looking at opening an office in a state that levies a sales tax on services. Can anyone share their experiences with that? If a plan pays for our services, are they exempt from the state sales tax? If an employer pays for our services, I assume we'd need to collect the tax? Thanks for your help!

I doubt it. In Virginia, a nonprofit must not only meet one of the listed categories of eligible entities but also be listed as one of the 200+ named entities that have received legislative approval for exemption from state sales tax.
Although I don't think Virginia is typical (because of statements I have heard about other states), and most services are exempt from sales tax in the Commonwealth of Virginia, I doubt that many states do what you are asking.

Theresa Lynn

You can find links to the Department of Revenue for each state here:
http://www.sisterstates.com/