Black lines while painting
If painting directly on the map, outside of the borders of your UV, fixes it, then it is a filtering/mipmapping issue that can be solved by increasing the bleed.

Don't worry about what your texture looks like out of the borders-- don't worry that it looks weird.  It's supposed to look like that.  That's not an odd image, an odd image is an image without any painted margins.

How much bleed should you use?  About half of the smallest distance between UV islands.  Ideally, your UV map is so well arranged that all verts of all islands are equally spaced and your entire image gets painted with bleed.

Increasing the bleed alone is not enough; it only paints bleed when you actually paint.  So in addition to increasing bleed, you need to actually paint over those edges again.  From the looks of your image, you painted, then increased bleed, then painted some more, but did not necessarily overpaint areas you already painted.  Which could easily explain your edges appearing only in some places....