I more or less have to answer my own question.
Apparently, our implementing partner for Dynamics CRM decided to use a new (?) field (called ahs_accountid) for maintaining the relationship between the contact and the account, which explains why the "original" field (accountid) is null everywhere.
There are still a few strange things about this, but they are not in my own way anymore.
* when using fetchxml with no attributes specified, the field ahs_accountid is returned (among many others)
* when doing the same and explicitly specifying ahs_accountid as an attribute, it is NOT returned (while others also explicitly specified are)!
To me, this still points to some inherent problems behind the scenes (read: a bug) that led me on a false path.
For now I am happy to always include all attributes, but that may change in the future.
I'm mostly leaving this here for people struggling with similar issues.