Oh, so it was. While changing the layout, I peeked around at the WP tables and decided to ‘merge’ a couple of older MT-related categories with the appropriate ones. To my surprise, I noticed that the rowcount (or, the number of posts in a category) was actually stored in a separate field in the wp_categories table. I have no problems with that (usage of the count function is generally not recommended).
It looks like the WP bug I mentioned before, has everything to do with the ‘upload image/send to editor’ procedure: the bug is persistent when you specifically link an image to a page. For now, linking to an image directly will do.