Find out whose turn it is to buy the croissants
There are two categories of solutions to this sort of problem that I'm aware of: biased lotteries and filtered/generated random sequences.

First, let's dispense with easy but wrong solutions that keep no state.  Any lottery-style solution that maintains no state will have the number of wins in a binomial distribution, which fails the "as many times" criterion.  You can select a random sequence that picks all people equally (just going around the list does that; permutations provide randomness), but once people start going on vacation your sequence now has holes.  Unless you keep track, you will again find yourself with binomial distributions instead of maintenance of equal effort.

Let's also commit to having actual randomness.  You might want this so that, for instance, a person cannot schedule their vacation on the basis of a deterministic algorithm so that they are never present when it is their turn to buy croissants (until they use up all their vacation days, I suppose).

So, on to the two types of solutions.


To construct a biased lottery, first note that we can pick from pretty much any continuous distribution (with finite deviation) to generate numbers for our lottery.  The loser can then be the person with the lowest number.  Then the simplest bias is to keep track of whether each individual has bought more or less than their share.  You can measure the bias in units of croissants.  You can tune the degree of randomness by changing the width and shape of the distribution--this will also determine how far away any individual can get from "the same number of times".  Gaussians are easy; they allow for reasonable surprise without having tails that are too long ("unfair").  So the basic shape of the solution is (in Scala code)

case class Employee(var bias: Double) {
  def eat         { bias -= 1 }
  def buy(n: Int) { bias += n }
  def roll        = bias + stdev * Random.nextGaussian
}


You can keep track of who bought last and give them a hefty bias bonus (e.g. 10*stdev) to keep people from buying twice in a row save in the edge case where vacation structure allowed everyone to have bought "last" time.  (i.e. you buy, then go on vacation.)  Same thing for not being present on the day they're selected.  (If someone is absent every other day they eventually will come up as they burn through their bias bonus; I consider this a feature rather than a bug.)

So, you collect your list of present employees for the day, have them all roll for the lottery, pick the lowest, and update.  You can choose whether to have the buying bonus be equal to the number of employees (good when the cost is negligible but the trip to get croissants is burdensome), the number of employees present (good if the trip is easy but the cost is burdensome), or something in between (to acknowledge both burdens).  It's probably better to only have the "eat" penalty for people who are present, but you can do it either way if you feel that merely being on vacation doesn't give you a right pitch in less.
To construct a filtered random sequence, first you need to generate a random sequence.  Shuffling a list of the employees is as good a way as any to start.  Just go through the list, in order, from day to day.  If someone can't buy because they're absent or can't be told or bought before, skip them.  Now you have a problem: you're accumulating people who have been skipped.  That's okay, though.  When you get to the end of your sequence, append the list of skipped employees to the full list before shuffling.  Now the probability of coming up is proportional to the number of times you've been skipped, which maintains the "same number of times" property.

If you use a standard shuffle, it's also particularly easy to quantify the randomness when there are no vacations.  If you picked people completely at random, the knowledge of who was to bring next would contain $\log_2(N)$ bits of information if there were $N$ employees.  Instead, however, only $N!$ instead of $N^N$ possible sequences are allowed, so the information is reduced by $\log_2\left[\left( {N!} \over {N^N} \right)^{1/N}\right] \approx -{1 \over {\log(2)}} + {\log_2{\sqrt{2 \pi / N}} \over N } \approx -1.4$ bits (for large $N$; for $N=10$ it's $~1.14$).


Personally I favor the biased lottery solution as the control over the randomness is better.  With filtered sequences, you can come up with more complex ways to generate sequences.  For example, rather than taking a random permutation, perform local swaps out to a certain distance, or allow swapping of people out of the pool entirely (but they go onto the skipped-list)—but these things require more algorithmic effort.  With the lottery, you just adjust the standard deviation.