3d track stabilzed video?
As you must have already figured out, it is better to avoid shaky, unstable video. 

It is possible to use 2d tracking to stabilize the video first, and apply the shakiness later using the 2d stabilization node in the compositor, but in reality it makes no difference, because you still have to track the video to stabilize, and the tracker will still have a really hard time tracking elements that are blurry, or shaky. If you are going to do motion tracking, might as well do it only once. Additionally all errors induced by the stabilization will only make solving the motion harder.

You can use one of the presets for motion tracking for blurry footage or fast motion.



If the movement is too much from frame to frame enlarge the search area, so that blender can find the tracked feature in the next frame:



And yes enlarging the search area requires more resources and will slow down the process.

(if the search boundbox is not visible enable it on the marker display section)



But don't expect miracles. If the original video is blurry, distorted, shaky or has artifacts caused by rolling shutter, etc, tracking will require a lot of extra work. You will need to adjust the trackers manually, when the autotracking process fails. It will probably take less time to do the shot again and keep it sharp (use a fast shutter speed), you can always make it shakier or add motion bulr in postproduction.

Read: 

Some Data Failed to Reconstruct, Motion Tracking

and

How can I get better results when doing camera motion tracking?



But for the sake or argument, let's pretend for a second that you did stabilize the video successfully. Then you would face two new problems:

1- The edges of the video will either be cropped, or you would have repeated pixels there where there is no information to fill the frame. To fix that you would need to render the stabilized footage on a much larger canvas and who knows how that would work to determine the field of view (combination of lens and sensor size).

2- The original motion blur of the video will not have disappeared at all from the frames, it will be even more obvious, again making tracking inaccurate.