Posso risponderti solo per quel che riguardo Xml.

Sicuramente non è il modo più efficiente di memorizzare i dati, però è molto comodo, quindi probabilmente ti conviene cercare una buona implementazione di Dom o Sax in C. Tra l'altro ti permette di gestire abbastanza bene l'integrità dei dati.

Ora che mi viene in mente, MySQL distribuisce un "embedded server" che puoi usare appunto dentro i tuoi programmi. Non l'ho mai usato, quindi non ti so dare informazioni sulle prestazioni ecc. Attenzione che se lo usi, legalmente non puoi dare via il tuo programma senza i sorgenti, oppure dovresti comprare MySQL con la licenza commerciale.

Se poi trovi le librerie C di cui parlavi fammi sapere per favore, mi interessa.