Yow, that looks messy.
Here's what I'd do: Shift-click on the shapes you want to keep, cut and paste them in a new layer. Delete the old layer with all the 'hash marks' and stray points. This
might be quicker since there are fewer keepers and they will be easier to select.
Alternatively, it might be easier to use the lasso to select the 'hash marks' and stray points instead of clicking on them.
As for optimizing AutoTrace, I haven't used that feature...sorry. Does it do this with any image or just this particular image?