You're right, the shaped plastic pins on the plug from the power supply don't match the motherboard socket exactly. However it is keyed in such a way that it can fit. On the pic of your motherboard in your first post, there's a pattern of square and rounded square holes. The square pins rounded on one side will fit in a square opening if needed, but the placement of square pins and square holes in the socket will ensure it only matches up one way.
Yes, the plugs can be a bear even on older equipment since they typically get plugged in once from the start and aren't touched again. Sometimes the plastic molding is just slightly off in size and requires a lot of force (but you don't want that plug loose at all or you'll have a loose...