Accurate auto focus locking is topic that is discussed in several Nikonians forums quite often. One of the reasons for some baleful comments about autofocus problems is the sense that Nikon DSLR bodies are so powerful that it essentially boggles the mind that some details or textured areas on some subjects just don't provide enough information for the D800 (or the Canon 5D MK III, or the Nikon D4, or the Canon 1D X, and so on) to accurately lock focus.
Without a sample photo (and I hope you get your computer back soon of course) it's still possible to offer a couple of suggestions. So here are some points to consider (and I apologize in advance if you've already considered some of this):
1. Whether a subject is far away or distant, large or small, close up or macro, the target has to contain detail that is large enough for one of the camera's AF-sensor points to actually detect.
2. Check your D800 manual for an illustration of the sensor points in the viewfinder. You'll see that quite a few of the sensor points are cross-type. That means they're designed to detect subject detail in both vertical and horizontal directions - much more accurate and useful for a much greater variety of subjects. The remaining sensor points are a bit more finicky because they detect information only vertically (or generally vertically - diagonal counts too).
3. The very latest lab testing by experts using a variety of high-end camera bodies (including Nikon and Canon), show very clearly that even in lab/testbench conditions, the exact same subject in the exact same lighting shot consecutively with the exact same camera and lens produces slightly different autofocus accuracy results from shot to shot. The cluster (on the resulting chart) is almost always within the accuracy tolerances with which the camera and lens have been engineered and manufactured. The point is that in the field (street shooting, landscape shooting, macro or flower shooting, birding, etc., etc.), small changes in position, selecting a slightly different autofocus point, respect for the greater inherent accuracy of cross-type sensor points, and making use of sufficient light for the camera and lens combination to operate in something close to their sweet spot, can all create a huge improvement in focus accuracy.
4. The better the light, the more generally accurate your autofocus system. That it is now possible (beginning with the Nikon D700, really) to make amazing photos in light so dim that as recently as 10 years ago anyone observing would have laughed out loud at us, is all well and good. The reality is that what our eyes often perceive as adequate light is, for the camera and lens combination, sometimes too dim for the most accurate autofocus. The message here is that more and more, as we rely on cameras such as the D800 to shoot in very challenging lighting conditions, we should really check metering very carefully.
For example, a scene for a matrix or zone meter that works out to 1/125s, f/5.6, ISO3200 seems perfectly usable unless you've chosen a focus target within the scene that is simply too dark or lacking sufficient detail for the AF system to get a proper lock. Consider that metering for exposure and AF system accuracy are two separate sub-systems in the camera. They're related to some extent, but largely independent. A usably metered exposure setting does not guarantee an accurate AF lock.
5. The focus confirmation LED in the viewfinder is an important tool. Any camera AF system can get a partial lock, make a shot, and then disappoint us with a soft result. Using the viewfinder provides visual access to the AF confirmation LED in the lower left corner of the 'finder.
6. All autofocus systems are inherently inaccurate at macro distances. The vast majority of flower, insect and fine detail macro shooters use manual focus. One of the best tools a photographer can use for accurate macro focusing is a focusing rail onto which the camera can be mounted (with the rail itself mounted on a tripod). A focusing rail provides very fine fore and aft positional adjustments. The other important tool for macro and flower shooting, I think, is a really good manual focusing screen (which also works properly when you switch back to AF mode).
There are two problems with respect to a replacement focusing screen for the D800. First, it's no longer a DIY thing - only the Nikon Service Center can make the change properly (for a fee of course). Second, Jim Lakey (the founder and owner of BrightScreen) just passed away and the site has been taken down for the time being and no orders are being accepted. And no other third-party focusing screens for the D800.
Still, for close-up or macro work with still subjects, I really recommend manual focus.
7. The differences you've noticed between viewfinder-based AF (phase detection) and live view focusing (contrast detection) are there by design. A live view focus point can be chosen just about anywhere on-screen, compared to the fewer points that can be selected in the viewfinder.
8. Handheld shooting works in many, many situations, but some photographers aren't aware that their shutter half-press to lock focus is inconsistent. Frequently, photographers who are noting a high percentage of mis-focused or blurry shots don't realize that after they've half-pressed the shutter button they're unaware that they've been inadvertently slightly lifting their shutter finger but then re-locking focus on something other than the original target. An imperceptible finger tremor (simply from holding position for more than 2-3 seconds - it can happen to literally anyone, young, old or in between and in any physical condition), a gust of wind, and several other things can cause the problem.
It's one of the reasons that many shooters prefer the AF-ON button for focus locking. If a shooter fully enable the AF-ON button on the back of the camera, and disable the shutter button for everything except the actual shutter release, certain problems are solved. The AF-ON button method is particularly useful for shooters who need more than a couple of seconds after focus lock to actually press the shutter button. The longer someone is handholding a camera and looking through the viewfinder using a half-press, the greater the likelihood that the camera will shift the point of focus all on its own.
9. The other problem with handheld shooting and some tripod shooting, is that same shutter button. Many handheld shooters who've locked focused (either with a half press or with the AF-ON button), press down the whole camera very sightly when they fully depress the shutter button. That sort of technique error causes two problems. First, the camera is moved ever so slightly during the shutter release, which cause a soft or blurred shot. Second, if the camera is set to AF-C (continuous autofocus), the slight downward movement of the camera can cause the focus point to shift just as the shot is taken.