So which is the truth?
This is speculative, but given the Professor's absent-mindedness it's quite possible that he didn't do all the proper paperwork when founding Planet Express in 2961. If so, it wouldn't have been until a true bureaucrat like Hermes was hired that the paperwork would have gotten done properly and Planet Express could be called an official company. In the episode "The Prisoner of Benda", we can see an Employee of the Year Award for 2993 for Hermes Conrad:
...and the earliest plaque is for Amy in 2992. So, if Hermes was actually hired in 2992 (thus making that the year Planet Express was officially founded, and when it officially started providing pensions, giving out plaques, etc.) then it would make sense for Zoidberg to get a 10 year award in 3002 during the episode "Insane in the Mainframe" (when Hermes informs him he hasn't paid into his pension fund).
So, even though Zoidberg has been with the Professor since he "founded" his company 50 years earlier, the company itself might have only been official on paper for less time. This would mean that typical company procedures, like keeping track of employee milestones or giving out Employee of the Year plaques, would have only begun occurring more recently. This is the best retcon I can come up with to explain the discrepancy. ;)
Apperantly Zoidberg was employed at Planet Express when it was founded, meaning that he is one of the senior staff. Planet Express was founded in 2961 according to theinfosphere. So that means he has worked at Planet Express for about 60 years.
Zoidberg has been working for Planet Express since day one because of the deal that he made with the Professor in "The Tip of the Zoidberg". In the episode "Mobius Dick", it is shown that Planet Express had existed for around fifty years, and that Zoidberg was there on the first mission. (Also, no he didn't have hair until he saw the Mobius Dick.) Therefore, Zoidberg has been working for Planet Express for a little over fifty years.