Do your smoothing groups match according to the UVs? You usually only want hard edges along UV seams, and smooth everywhere else. I would also recommend making a cage, as it can have a substantial effect on the quality of your bakes. I believe the Push modifier will make a cage pretty easily in Max.
I don't know if it's Toolbag itself or the way you exported the texture, for e.g. when saving the file after modifying it in Photoshop, it might have problems if you export a targa file with compression or a particular resolution it doesn't like. There's all kinds of variables that can result in bizarre Toolbag renders.…
Cages are super easy. With the Push modifier, you just dial up the value until your HP and LP are completely encapsulated. You want to keep as close to the original models as you can. If you have any tight spots where the LP or HP shows through, you can tweak the sub components around in those specific areas without having…