Here is where I am testing going forward, Cornell Soil Lab.
https://cornell.app.box.com/s/ryy6xgtwok5l85zzy9fgms1276drud0y Pay special attention to how they break down soil. There is what they call "inherent soil quality" and "dynamic soil quality". Inherent soil quality is that which comprises your soil, the composition of elements. Inherent soil quality cannot be changed in any great measure; your soil is what it is. At 2 million pounds per acre per 7" of topsoil, any appreciable component change would be very expensive. What can be improved greatly is the dynamic soil quality, basically the life in the soil. This is where all of the good soil building measures come in, composting, cover crops, minimum or no tillage and the like. A standard soil test does not measure the life in the soil, this is where comprehensive soil analysis shows off. Cornell Soil Lab contends that measuring soil life will tell the landowner where they are going with their soil improvement program long before a typical soil test.
I would look for a soil lab that is using either Morgan Extract, Haney or Mehlich III. These test methods are known to show plant nutrient availability better than other tests. I have started using plant tissue tests as a good measure of what is plant available. If the nutrients show up as normal in the plant tissue it is in the soil in an adequate amount. As you improve your soil life, nutrients that may previously been unavailable and not showing on the soil test may become available. Also, soil pH can change quite a bit during the growing season as plants have the mechanism to alter pH.