Well, the Japanese have tamed the virtual makeup down. Created for cosmetic giant Shiseido by Fujitsu, the following application can be found in kiosks across Tokyo:
More details on Engadget
And, if you are not lucky enough to live in East Asia, Walmart and the British drugstore chain Boots are piloting the following kiosk by EZFace. Unfortunately, it works on a static image and doesn't augmented live video feed, so it's not really AR.