Flightstats.com has a paid subscription (25usd/month) that comes with 250 historic flight searches. I haven't tried it myself yet, but am thinking about it for something similar to the OP.