Approaching a large machine learning problem I have massively rewritten my original question to further explain the problem.  It involves a regression problem on a dataset of about 2.5 million records.  My development has been done entirely in R.
The Problem
Description
The problem involves predicting costs of highway construction contracts.  Contracts are let in large groups statewide each year (called "lettings"), maybe once every other or third month.  Each contract is described by a series of payitems, which specify the materials, labor, and equipment required to do the work.  Each payitem is categorized by a unique code of seven digits.  The codes give a clue to payitem similarity.  For example, drainage-related items are under codes beginning with 542, and asphalt-related items begin with 406.  "Similar" payitems are typically similar in terms of the materials and equipment used.  The labor required to construct, however, may vary greatly, depending.
My goal is to predict a payitem unit price based on a history of bids going back 13 years.  Note that a bid occurs each time a contractor bids on a payitem in a contract.  Thus, if five contractors bid on a contract with 1,000 payitems, I can mine 5,000 individual bids from the data.  To date, I've mined nearly 2.5 million individual bids.
Target predictions should be consistently within 15% of the actual value.  Given that cost estimates are often inflated 10% - 15%, I felt this was a reasonable measure of success.
Predictors
To this point, the features I've selected for the problem are:

*

*Location (a regional descriptor)

*Month of letting

*Payitem quantity

*Payitem number

*Total contract value

*National Construction Cost Index (FHWA NHCCI)

*Union laborer prevailing wage for the month of the letting

*Relevant material and equipment cost indices

Obviously, material, labor, and equipment costs will drive the bid price, but there are other considerations I can't really model (noted below).
Based on my success thus far, I believe I've captured enough features to accurately model the data.  So, without identifying which contractor made which bid, there's not much more I can do in terms of useful predictors.
Preliminary Results
To this point, I've achieved around 90% success predicting the price of guardrail payitems (a data set of about 10,000 observations) and somewhat less with asphalt payitems (about 25,000 observations).  Other payitems, (like erosion control), are much harder to predict due partly to the nature of the work and materials, and the relative paucity of available data (~1,000 observations).  Thus far, I have had about 50% success.
What complicates accurate prediction varies greatly.  While I've managed to represent the costs of the payitems with a variety of relevant indices, there are myriad of other factors that can influence a particular bid, including distance the contractor and/or supplier is from the jobsite, potential "bidding wars" where contractors bid low on certain items to gain a competitive edge in bidding, or intentionally high bids because the contractor is not particularly well-suited for the work or suspects the designers did not adequately account for the scope of work.
The Solutions
Experience
Overall, one should expect strong linearity in the data, as quantity and price scale inversely.  However, there are price ranges where that assumption breaks down which may or may not be strongly related to the other features at my disposal (bids in urban vs. rural areas, seasonal price fluctuations, etc.)
My current solution has employed the following techniques:

*

*Scale and normalize all data (even category / binary values).


*Log transform features that show a strong non-uniform (but otherwise
non-Gaussian) distribution


*Remove the upper and lower 1% of outliers (validated by inspection of the data)


*Employ a chained ensemble of models
To elaborate on the 4th point, I initially tried a neural network and achieved 60%-70% success, but only after extensive optimization efforts.  After experimenting with other algorithms, I found I could get consistently higher (70% - 80%) with any one of a support vector machine, random forest, and gradient boosting machine.  Simple / geometric averages of these three models gave me another 3-7%, depending on how similar the model accuracies were.
Finally, if I took these machines and trained them again with the same hyperparameters, but appended the previous run's predictions to the original data features (creating a "chained" ensemble), I might see another 5% - 10% success increase.  Chaining an individual model in this fashion only resulted in over-training with loss on the validation set accuracy.
Next Steps
There is strong linearity in certain price ranges, and linear regression may perform quite well on some (or even most) of the data, but I have no easy way to split out the linear / non-linear segments without knowing the target price in advance.  Interestingly, (and perhaps it's intuitive), if I used linear regression as the second step in a "chained" model, (thus relying on predictions from previous non-linear models), linear regression fared much better, often performing almost as well as a non-linear model.
I've experimented with splitting the data using decision trees so I can segment it by its features.  They've proved helpful, but I don't yet have a good grasp of how effective it may be in reducing overall non-linearity.  Of course, if I could eliminate the non-linearity using decision trees and apply linear regression to the resulting datasets, I would certainly do that.
Looking at the non-linear solution I've developed, it may be over-complicated, but I don't know that it's necessarily a bad option.  To the point, I have discovered that the networks didn't need to be optimized that well to provide a similar level of success.  A poorer level of optimization only resulted in a 2% - 5% loss of success.  If there is a feasible solution here, it would have to involve finding the breakpoint where the overall accuracy depends more on the number of models in the ensemble than the degree of optimization applied to them.
These are the two primary solutions I see in approaching the problem as a whole.  What complicates implementing either of these is the volume of data (2.5 million records) and individual payitems (43,000+).  As suggested in the comments, using the payitem number as a feature may prevent similar payitems from benefiting from the patterns the model learns from other payitems.  This could prove problematic especially where some payitems are poorly represented, but are otherwise very similar to other, better represented items.
Again, I apologize for the length, but I hope it explains the problem more clearly.
 A: Nice, exhaustive write-up! I want to propose an additional consideration or two. Most importantly, instead of building separate models for each payitem that you integrate the massively categorical nature of the payitems into a hierarchical modeling framework. This approach has several advantages: 1) by pooling the data, it would improve estimation for the sparsely populated payitems, 2) it would "shrink" the parameter estimates and their standard errors, and 3) would more appropriately account for the variability in the data versus building each model separately. Here's a paper that focuses on leveraging zip codes in a direct marketing modeling environment that describes a Bayesian approach to this:
http://www.people.hbs.edu/tsteenburgh/articles/Steenburgh_Ainslie_and_Engebretson_(winter_2003).pdf
But you aren't limited to a Bayesian approach. When this paper was written, hierarchical Bayesian frameworks offered significant advantages over the challenges traditional, closed-form or "frequentist" models faced in, e.g., inverting a massive cross-products matrix such as is required when evaluating ~35,000 zip codes at one time. However, that was then and this is now. Today, there are workarounds to the massive size of your data that have put "frequentist" approaches at parity with Bayesian techniques. These include so-called "divide and conquer" algorithms which, in essence, can be analogized to massive random forest-like approaches in that -- instead of just creating a thousand or so mini-trees (Breiman's original forests or ensembles) -- one builds tens of thousands of mini-models and aggregates the results on the back end. Here's a recent review paper on D&C: 
http://stat.rutgers.edu/home/mxie/RCPapers/split_and_conquer_rev1_final.pdf 
Of course, this method would be still be a challenge today on a single CPU or laptop as these techniques only really become an advantage on a multi-core platform.
There's plenty of literature to review regarding hierarchical models... starting with Gelman and Hill's Data Analysis Using Regression and Multilevel/Hierarchical Models. Otherwise, I'm agnostic as to the specific functional form the regression should take beyond a hierarchical one. It could be that exploring different approaches to analyzing one, two or a few of the payitems would provide direction towards answering that question. 
