Do full nodes store the complete merkle tree or do they regenerate it when creating a merkle proof?
Bitcoin Core, in its BIP37 implementation, will compute the Merkle proofs on the fly. It does not store the blocks' Merkle trees anywhere (only its root is stored).