A B757-200 Captain reported he is uncomfortable with his company's fuel planning policy when operating from the continental U.S. to the Hawaiian Islands; stating that significant over burns are not uncommon and planning should reflect that.

Narrative

Flight was planned to land with 8;500 pounds. Since I felt this was inadequate to allow safe diversion should destination weather deteriorate; I added 1;500 pounds. We should have landed with 10;000 pounds. We flew only 1;000 feet above planned cruising altitude; in LNAV with flight plan cost index and Mach. Headwinds were stronger than forecast; sometimes more than twice forecast; which caused a steady decrease in expected landing fuel. Dispatch was informed via HF radio. The aircraft landed with 7;000 pounds. We burned 3;000 pounds more than forecast. My concern is that when flying to the islands; this situation is not uncommon. Bare minimum fuel planning leaves us with no margin for error when planned cruising altitude is not available; or headwinds stronger than forecast. Also; the flight plan fuel burn is usually lower than what actually occurs; even when flying planned Mach and cost index. Also; weather reports are sometimes inaccurate; making it impossible to know if approaches can be successfully flown. Flight plan fuel should be adequate and allow for deviations in altitude; winds and destination weather; and should always allow enough to safely divert.