I'm no Dr., but does the pain seem to coincide to when the plane pressurizes? That might suggest an inner ear or eustacian tube (however it's spelled) problem. You said you've tried allergy medicine; does that include a stand-alone decongestant like Sudafed (without all of the other drugs) or a nasel spray like Afrin? (I'm certainly not recommending that you try these or any other drug remedy without speaking to a Dr. or pharmacist, but you might ask them about it)

Also, migraines can be caused by food, so you might consider whether there may be some food, drink, preservative, etc. that you only and typically consume at airports prior to your flights.