Can I publish old company event photos (for a Company book that includes "Our History") without all the employees signing release forms? I'm having trouble even finding/contacting the old employees since it was so long ago. I need to know the legality in doing this.
Yes, you can. I'm not an attorney, but a non-commercial company book would seem be an editorial use. You don't need model releases for editorial use. If you are really concerned, you might want to either consult an attorney who's up to speed on this kind of intellectual property or get in touch with your local chapter of the ASMP to see if they can offer a definitive opinion.
Will it be the company publishing it? If so the law is probably different from if it's you yourself. Also, the law of course differs per country (and maybe per state in some countries like the US).
Best see a lawyer about this, the company should have a legal department who can help (or can get you in contact with someone who can, and should pay for legal advice if it's them doing the publication).