Hmmmm. Before you turned off autocomplete did you try click the Clear forms/passwords option?
And I guess you have also clicked Clear History at the bottom of Internet Options page?
If all else fails, and it matters still, how about going to
www.airlineappointments.com and seeing if there is an option to remove it, or ask them to?
bug