The shear flow of microfibrillated cellulose dispersions is still not wholly understood as a consequence of their multi-length-scale heterogeneity. We added carboxymethyl cellulose, a charged polymer, that makes cellulose microfibril dispersions more homogeneous at the submicron and macro scales. We then compared the yielding and flow behavior of these dispersions to that of typical thixotropic yield-stress fluids. Despite the apparent homogeneity of the dispersions, their flow velocity profiles in cone-plate geometry, as measured by rheo-MRI velocimetry, differ strongly from those observed for typical thixotropic model systems: the viscosity across the gap is not uniform, despite a flat stress field across the gap. We describe these velocity profiles with a nonlocal model, and attribute the non-locality to persistent micron-scale structural heterogeneity.