They can still move with zero fuel, just very slowly. This is to avoid AI fleets getting stuck in limbo due to poor planning.
Actually, they will move at the same speed, however the NPR AI is such that a fleet which is out of fuel is forced to attempt to return to the nearest refueling location (usually home planet), which is one of the things that causes endless short increments as if the path to a refueling base is through a high-danger system, the NPR fleet will jump back and forth endlessly.
AI does not use maintenance. Also, jump shock is much shorter for AI if I recall correctly.
IIRC, Steve said NPRs are supposed to have the same jump shock rules as players, although they may have shorter recovery time on average if they get 100% crews by default (I'm not sure if this is the case under the hood). Also IIRC, the supposed shorter jump shock was really due to common confusion about the rules of jump gate transit, which made NPRs look like they could transit every 5 seconds - this was changed in one of the 2.x versions I think, to prevent some of those endless short increment loops.