Critter gives some good information. When I started everyone said we were a recognized 501c3, but I couldn't find any evidence. (And we also had confusion over tax ID's.) So I spent quite a bit of time on the phone with the IRS reps - who are truly wonderful. Thank goodness it's an 800 number. (But note - unlike other IRS lines, hold time is minimal.)
Actually, they were very patient about trying to look us up by name - but it did take awhile. As Critter pointed out, you have to check for multiple ways the name could be listed.
Our IRS rep was a real pro and kept asking me questions and looking it up different ways, various spellings, by address, by phone number, etc.
Also there is an online search at
www.irs.gov/exempt/display/0,,i1%3D3%26g...icId%3D15053,00.html.
However, it may not be totally up to date at any given moment, you probably still need to call if you don't find it.
And, no - we weren't set up.