I can understand the logic on both sides. My PI's policy has always been that as long my name is first and his is last, he doesn't care how many other names are in between. If someone provides reagents that are unique and unavailable elsewhere, we end up adding them as coauthors. It seems only fair to do so. I think the rule in my head is - if you provide data for any of the panels in the main text or you provide a critical reagent that was unavailable commercially, you should get the opportunity to be a coauthor.
The problem with adding tons of coauthors to a paper is that it's not fair for the middle authors. Personally, I've declined to be a coauthor on a paper that I spent literally 20 minutes taking microscope pictures for. It didn't seem fair to claim credit for a quicky experiment like that when the other coauthors spent months slaving away creating cell lines and constructs.
I think one thing that helps a lot during collaborations is a frank discussion on who gets what credit on the paper. In my experience, it works really well when you can get everyone to sit down early in a project and say: "Okay, person X is doing the key experiments so he'll be first, then Y, then Z for providing cells, etc..."
Miz, I think that's harsh that you didn't get credit for a crystal structure. That's a ton of work - it sucks that you didn't get a coauthorship for that. I'd be kind of upset - you're a better person than I am!