I have added DTT to the extraction buffer, and or I have boiled DNA prior the PCR reaction, I have also used kits and no-kits for the extraction but the PCR results are still poor.
My lab has a very difficult time amping DNA from fixed/paraffin-embedded samples. It usually takes some modification and a few tries. In general, the best thing we've found is to double the Taq and to sometimes dilute the DNA (we use 3-5 mg of tissue per extraction in 100 uL of solution, then use 1 or 2 uL in the PCR rxn; sometimes we dilute the DNA by half and get better results).
Normally glutaraldehyde doesn't crosslink DNA, only protein (http://onlinelibrary.wiley.com/doi/10.1111/j.1365-2818.1984.tb02550.x/abstract).
But probably the chromatin is crosslinked "around" your DNA you want to amplify.
Glutaraldehyde fixation is reversible to a certain degree (this paper found 86% using acid and borohydride: http://www.ncbi.nlm.nih.gov/pubmed/6421586). Maybe adding a protease-cocktail helps.
I suggest that the deparaffinized tissue sample (≤25 mg) in a microcentrifuge tube, will add Proteinase K and Incubate at 55°C overnight (12-16 hrs), this ensures maximum yields of DNA from even tough-to-lyse (collagen-rich, fibrous, etc.) tissue samples. Transfer the digestion to 94°C and incubate for 20 minutes. Best regards.
Thank you for mentioning our 1983 paper on reversible fixation using formaldehyde. Obviously, our abstract was not clear enough: Using formaldehyde gives you an efficacy of the protein fixation comparable to that achievable with glutaraldehyde. In our hands the formaldehyde fixation could be reversed by 86%, whereas the fixation by Glutaraldehyde is not reversible. If I recall correctly, V. Jackson (Cell 15, 945(1978) used formaldehyde to stabilise histone/DNA complexes during purification and later reversed the fixation on the purified isolates by boiing for analysing the histones.
So, dear Lucia, I would go for the proteinase K/ heat protocol.
I am all ready using the proteinase k/ heat protocol and added some DTT to the extraction buffer, and seems to work better (a Little), and it sounds good the sonication protocol, I will try with this also.