Keep it slow. Don't change the extrusion width--that will make it worse (or at best, not change anything). Extrusion width alters the slicing, increasing the space between passes in addition to changing the extruder speed.
Underfilling is caused by low pressure in the extruder. The acceleration parameters that work beautifully for ABS and PLA just aren't close for Ninjaflex. I've found the same issue with many flexible filaments, but it is usually at the ends of each line--sometimes they don't connect with the perimeters. The middles of lines are good and well connected.
Printing very slowly helps(<10mm/s)--also Adding Extra Restart Distance and Coasting Distance may help.