My apologies is most or all of this is already obvious to you.
The first thing you need to define is whether you want to look at all the records for a randomly selected employee or all employees on randomly selected days in a time period or randomly selected employees on randomly selected days or something else entirely.
Also, do you have the same sampling probability for an employee who works for two months and an employee who works for two decades? Would you need to reweight the data to get a meaningful estimate?
These two are intertwined. You might get a simpler sampling system that leads to a more complex weighted estimate versus a more complex sampling system that leads to a simpler unweighted estimate. Which is better overall is hard to say, though I suspect that the latter would be preferable.
One possibility that you've probably already thought about is randomly selecting employees and picking a random time for each employee in your sample. Depending on what you are trying to estimate, this may lead to overrepresentation of short-term employees, which would require reweighting. Another choice is randomly selecting a certain number of time periods and then randomly selecting one employee from each time period. Again, depending on what you are trying to estimate that may lead to overrepresentation of long-term employees.
In the latter case, an employee who stays for a decade has a ten times larger probability of being selected than an employee who stays for a year. If that's what you want, great, but if not, you have to downweight the first employee.
It's tricky to visualize, but one way of thinking of it is to figure how you would estimate things if you had all the data. Would you compute an estimate for each employee and then calculate an unweighted average of those results across all employees? In that case, you'd want to make sure either that the short term and long term employees have an equal probability of getting into your sample or you'd want to adjust the weights, giving greater weight to those employees who, because of their shorter tenure, have a smaller probability of getting into your sample.
Or would you just get an estimate for each payroll record and average across all records. In that case, you'd either want to make sure that longer term employees had a larger sampling probability or you'd want to adjust the weights. This time the weights would go in the opposite direction. Employees with longer tenures are underrepresented and need to be upweighted.
You might consider changing the sampling probabilities, so that your chance of choosing an employee is some function of how many payroll records that employee has.
You also need to define the cost of sampling. This may vary, of course, by the sampling plan. So ten time cards from the same employee may or may not cost as much as ten time cards from ten different employees. These costs will define whether one sampling plan is preferable to another sampling plan.
You also need to define the desired width of your confidence interval. Even better would be a function that translates the width of the interval into a dollar figure, so you can find the optimal tradeoff between sample size and precision. But in many applications, there is no obvious way to quantify the economic benefit of a narrower confidence interval. But you do have to get at least a commitment to the desired width of the confidence interval. Otherwise, you have no rational basis for choosing a sample size.
The formula for the width of the confidence interval should take into account both the stratified nature of your sample and the clustering effect of multiple measurements on a single employee. It might be a weighted mean or proportion, which adds another layer of complexity. But any good book on sampling (e.g., Levy and Lemeshow) should have all the formulas you need.
Do you want a single confidence interval across all years or a separate interval for each year? If you get yearly intervals, do you care if the intervals are independent of one another or not. If not, then getting the same employee in 1986 and 1988 is irrelevant.
You might avoid some of the complexities of cluster sampling if you deliberately only choose one record for any employee in your sample, but it is unclear from your description if you can do this.
You should definitely consider a sample of employees stratified by office (e.g., get exactly two employees from each office). A stratified sample by work period is another possibility (e.g., make sure that each month is equally represented in your sample). Maybe you should consider a doubly stratified sample. A stratified sample may or may not be better than a purely random sample--it depends on whether there is a lot of homogeneity within strata. But in your setting it seems like such an easy thing to implement that it's almost a no-brainer.
A cluster sample only makes economic sense if the cost of sampling multiple records per individual is a lot cheaper than sampling the same number of records from different individuals. I doubt that is the case here. So avoid cluster effects in your estimate unless it is impossible to avoid them.
Finally, if the sample is needed for some regulatory reason (e.g., to satisfy an IRS audit) then you should consider what the regulatory agency wants to see. They may have some guidelines on how to sample in a way to meet their goals. No point in optimizing the sampling plan for the benefit of the CFO if the regulatory agency is going to shoot down your sampling plan if they consider it inadequate.
I hope this helps.
-------------------------------------------
Stephen Simon
Independent Statistical Consultant
P. Mean Consulting
-------------------------------------------