The pillow has been a major pain in the butt for me over the years, but I think I found a solution.
Recently, I recently stumbled onto the Ikea travel pillow which at least for me seems to be the best pillow I have used. It's an inflatable pillow that costs $5, but it doesn't have that waterbed balloon effect that I hate so much from inflatable pillows. The inner pillow bladder weighs 1.1 ounces. The pillowcase which comes with it is rather thick and weighs 2.9 ounces and is really comfortable. I had a long debate with myself whether or not to carry those extra 3 ounces because the stock pillow case is very nice, but chose not to. I had a few of those little blankets from flights (Delta) and cut one up to make a lightweight pillowcase, so the total weight is dropped down to 1.5 ounces.
I just got back from a segment on the AT and used it head to head against the Exped and there was no comparison. I got home and gave my Exped to my daughter.
Pillow blown up next to 2 liter bottle for reference:
https://www.dropbox.com/s/mwndfzyi0buebom/2012-08-08_10-45-47_930.jpg
Two parts of the pillow:
https://www.dropbox.com/s/eipxacl1tlkoweb/2012-07-03_01-00-08_982.jpg?m
Oh, I also picked up a 3 ounce pair of flip flops from Ikea in the travel section which worked out well as my camp shoes.