Маркиз де Велада — это испанский дворянский титул, де Велада в нём не является фамилией, а обозначает отнесённость к территории под названием Велада. В этом сочетании действительно склоняется только слово маркиз: маркиза де Велада, маркизу де Велада и т. д. Если же де Велада становится фамилией, тогда её следует склонять: де Велады, де Веладе и т. д.