I've never been in a position where i was making budget decisions or even recommendations, so i may be way off (sorry if i am), but it seems to me that the most sensible means of constructing a budget would be a formalization of what Steve mentioned. Be careful with the money, and if it's possible to be under budget let management know. If it's not, let management know and explain why (actually it would probably be best to explain either way...)

It seems to me that basing a budget largely, though certainly not exclusively, on past budget vs. expenditure numbers is a fine idea. What is necessary is realizing that costs are not going to be the same year after year for innumerable reasons (changing prices, special projects, changing office locations, etc.). I would think that a company should set up a reasonable budget for each department, then make sure to set up an overdraw budget: money held in reserve in case the other budgets are exceeded. Anyone needing to tap that reserve should have to document how and why their given budget was exceeded. Any money left over could be carried over into the next year's overdraw or distributed as bonuses (perhaps weighted so those who are most financially responsible get the biggest). As Steve mentioned, most comapanies have vast amounts of information in digital form. I should think that it would be simple enough to continue refining budgets year after year, so the overdraw budget would only ever be needed for emergencies or unplanned expenses.