[thejeff]

Generally, only some units will be starving. IIRC, if not all units in the province can be fed, the rest will starve. Which ones are randomly chosen.

It's possible, and fairly likely, that he has scouts with supply items along with the force. They'll stay hidden instead of attacking, so you won't see them in the battles, nor will he risk losing the supply items.