Are "de" and "cu" interchangeable in this type of sentence?
No they are not !!. "cu" means "with" mayonnaise not "of" mayonnaise, which is pretty different.