Complexity doesn't mean apparent complexity. An organism can have the need to perform very specific functions that need specialized genes and the respective machinery it builds. However, that task isn't of concern for an organism who doesn't live in the same environment performing the same tasks as the first organism. So an organism may be complex as in it perform novel processes inside it's cells, but that doesn't manifest in visible features, instead being observable by the organism surviving in conditions where it shouldn't.
Which conditions are these can be many, such as thriving with certain nutrients being present at lower concentrations, or being able to better withstand sudden temperature shifts in it's environment. These conditions can be very specific and only seem unusual if you had a population of the same organism without the gene which you could compare to, as they might need those additional genes to compensate for shortcomings due to other prior genes that had a net positive effect on their survival and as such were not worth abandoning.
Another effect to take into account is emergent properties. Certain organisms might be more efficient with their genome size because they have certain genes that, when combine, can provide the same services as specialized genes. For example, you could have a gene dedicating to coding for a protein that, in the presence of a certain substance, binds to some receptor. However, a creature with a more efficient genome could have a protein that performs that function to an acceptable standard when in the presence of a second protein, even if those two proteins by themselves are specialized for performing a different role. So the second organism simply increases it's expression of both proteins when signaled to do so, instead of accessing a specific genome for a specific protein for that task.
Do note that I'm not a biologist, so none of the examples I gave are referring to a specific, real world process.