Black triangle bake artifacts issue

I baked my ao map but it created some bad triangle artifacts. Why? How do I resolve this?

Smooth shading is On? (on the targeted mesh)
Did you try to subsurf the targeted mesh first?
There are more.
Anyway, BI baking is problematic at least. Let’s try to find a workaround.
Cycles baking is coming soon.
It is already here (under experimental builds) and it is already much superior.

Remove any double vertices or duplicated faces
Ensure all face normals are consistent. recalculate normals of selected faces with Ctrl+N

@richard Markflew I tried removing doubles and the normals are correct. I still get the same results. If it helps, my mirrored uvs from which I applied the mirror modifier are stacked on top of eacher as I don’t want to texture the same spot a 2nd time so I only halved it.

This is your problem: two parts of model occludes each other for baking engine. Try to bake only one half.