My guess is that you are being messed up by the bootstrap sample giving samples that don't have the same pattern of presence/absence as your original alignment.
If you want to avoid this, divide your column into blocks such that each block has the same pattern of taxon presence/absence, and then apply stratified sampling:
in the way that it is used for variance reduction:
For example, say we have two sets of taxa, one for which we have genes 1, 2, and 3, and another set for which we have only genes 1 and 2. Our alignment then will look something like this:
where in this example the first set of taxa (with all genes) is in the top part of the alignment and the second set in in the lower part of the alignment.
We then group the columns of gene 1 and 2 into a block P, and the columns of gene 3 into a block Q.
When we apply stratified sampling, we sample uniformly from the blocks separately such that we get the same number of columns in block P as in the original alignment, and similarly for block Q. I hope it's clear how we would proceed in the case of many blocks.
There are fast ways to do this, though that's not such a big issue here most likely. Here's a photo from the Doucet book on Sequential Monte Carlo:
It is my understanding that for the bootstrap one would like to do resampling in a way that mimics characteristics of the data were we to run "the experiment" again. In phylogenetics, the experiment is evolution, so if we think that the pattern of presence/absence is something set in advance of the experiment, then I think this is the right thing to do.
However, this says nothing about how the pattern of gene presence/absence is influencing your topology. If this pattern is contributing significantly to your topology, then you will get a lovely high level of support for it!
I'm curious what others think.