That's a good question, KE. Published, yes, but is it legitimate or of any value? I think if it's not vanity press (someone asking you to pay to see your work in print), then it's still legit, though to put your work on the web in a non-paying market is certainly not as prestigious as placing it in something like Asimov's. A quick search of the above mentioned link led me to both paying and non-paying. If a writer's goal is to see their work in print--then non-paying does the job for them. If the goal is fame and glory--maybe a good paying market is the only one that's worthwhile.
Honestly KE, I think all publishers are looking for is a story that rocks them. There are some great venues to get your work in print that don't pay a cent. I think they're of value. Alien Skin Magazine (alienskinmag.com) pays five bucks per story--not much, but they're a quality organization and they don't just publish anything that comes into them. I think it helps to be published in a non-paying market, provided the market is well-regarded. The main thing is though, that the writing has to do the selling. The story is key (it must be original--or some very imaginative new take on an old theme), the characters must be believable, and then you need to connect with the right editor at the right time.