NiCoMgOx and NiCoMgCeOx on commercial low surface area zirconia-haffnia catalysts have unusually high thermal stability (>= 2000 degrees C) for syngas generation via the methane partial oxidation process (J. Catal., 233, 36, 2005). Herein we report the results on accelerated sulfur deactivation (0.74 mol% sulfur in feed) and corresponding regeneration (at 800 degrees C in 1:1 O-2 + N-2 flow) over these catalysts. The NiCoMgCeOx catalyst, due to a larger mobility of lattice oxygen, showed a considerably higher resistance to sulfur poisoning; the higher mobility of the lattice oxygen in case of the NiCoMgCeOx catalyst may be related to the presence of CeO2. During the deactivation process, the selectivity for H-2 was decreased to a much greater extent than that for CO. Regeneration studies showed that even after complete deactivation of the catalysts, the original activity/selectivity of both the catalysts could be completely restored after a simple regeneration process. Based on their exceptionally high thermal stability, high activity/selectivity and easily regenerability, the NiCoMOx, and NiCoMgCeOx catalysts appear to be very promising candidates for the CPOM process. (c) 2006 Elsevier B.V. All rights reserved.