Duotrope is great for fiction, and they're starting on creative non-fiction, but it doesn't cover newspapers, magazines, and websites which deal mostly with news and information.
Either Writer's Market isn't what it used to be, or I have higher expectations than I used to. I'm starting to think that there is no really good central database. You probably have to go out and look at newsstands (and on the internet) to find your local publications, and do your own internet searches for other publications. Amazon might be good for finding out what print magazines are out there in various subject areas.