Are your headaches migraine-like, eg. do they get worse with light, loudness, movement, are they stingy and pulsating? Do you get ill (puking one time would have been again the antibiotics?) ? Do you get auras, eg. anything that falls under "weird neurological phenomenons"- lights, not being able to speak, read, geometrical patterns, anything?

Before I looked at your list, I bet at Histamine-intolerance, especially because of the symptoms you mentioned here and the fact that Ibuprufen works. I predicted lots of histamin-rich foods, basically everything conserved and/or fermented. You seem to eat a lot of cheese and fish- is the fish frish or canned?