Calculate years of service

I am looking if there is an Excel formula or macro that can calculate the years of service for each employee based on periods of employment and seniority date. In order for a year to be considered as a year of service, an employee must work a complete calendar year (January 1st through December 31st); otherwise, that period of employment (months) do not count toward someone’s years of service. The problem comes in because we have quite a few employees that have been terminated and rehired. Also, once obtaining the years of service, I am using VLOOKUP to obtain the vacation days from information located on the VacationTable tab. However, I can’t figure out the vacation hours, monthly accrual and daily accrual based on the vacation days.
Can anyone help me? I've been stuck for a while and can’t get this to work.
Please refer to attached file for better understanding of what I am trying to accomplish.