Yes, I admit this one was stupid. But cut me a little slack - last time I had to make network cables was many moons ago. And yes, I even got to make coax cables for 10 Mbit Ethernet. But no matter.
OK, so we got this spool of cable from a generic vendor with the cable labeled "ANSI/TIA-568-C.2". For some reason - looking at some pictures online, most likely - I decided that was to be wired according to the T568A layout. And wire them I did - a few cables, actually. Which worked fine in multiple jack with an exception of a Cisco Catalyst 2000 100 Mbit switch where they did not work at all.
Then I wired one cable to the T568B layout and it seems to work everywhere including that Catalyst 2900 switch. Given the T568C is said to have superseded T658B which in turn superseded T568A which is by now obsolete all of this seems to make sense. Hence it appears that the solution has been found.
Let me also take the time here to thank all those mailing list respondents whose guidance helped me figure this mess out. It always helps to have other minds to collect thoughts off of!
Ethernet over twisted pair
How to wire Ethernet Cables