I did have my roommate prepare the food. Another one of my roommates swapped/labeled the food and then went to class, no interaction. It was mostly because he didn't believe that I could feel it and that it was mostly in my head. (which I totally understand, I was pretty worried about that as well)
We switched out white flour for some almond flour. We also did another one where he sweetened something using honey and another using corn syrup. (I could totally taste the difference there though)
Certainly not rigorous, but enough to make me pretty sure it isn't entirely a placebo effect. I'm planning on getting a Celiac Sprue test at some point.
On the other hand, if a diet helps, and provocations after, say, a month (but without your knowledge) make things go downhill fast, you can be sure enough. Welcome to the wonderful life where you get to check yoghurt for trace amounts of wheat products, and pizza is a holy grail (one of my closest friends is coeliac, for people in Amsterdam area, Woodstone in Haarlem makes good gluten-free pizza).
That being said -- you don't need to find the optimal for the population. You only need to find the optimal for you. And so even un-blind testing is reasonably effective at that.
But here's the thing. You can't double blind yourself. That's the whole issue with blind trials. Double blind trials require that you do not and can not determine whether you are in the treatment group or not. Additionally, unless you're having an unrelated person prepare the food, w/o any knowledge of which foods are in the "paleo" group vs the control group, you're not operating double blind.
If it's just you and another person, it would be challenging to set up a double blind experiment (although i'd be interested to hear what you tried).