D.D. Kosambi writes that V.S. Suktankar's 1933 text-criticism rejected it. What do different critical editions say about that?
Since you are asking specifically about critical editions, here's the BORI edition.
Page 13 of the file, the parva starts with the said verse.
It is absent from the Critical Edition of the Southern Recension of Mahābhārata edited by P. P. S. Sastri. As you can see at this link, the first numbered verse is a dhyānaśloka that begins with śuklāmbaradharaṃ viṣṇuṃ...
॥ श्रीः ॥
॥ महाभारतम् ॥
शुक्लाम्बरधरं विष्णुं शशिवर्णं चतुर्भुजम् ।
प्रसन्नवदनं ध्यायेत् सर्वविघ्नोपशान्तये ॥ १
धर्मो विवर्धति युधिष्ठिरकीर्तनेन
पापं प्रणश्यति वृकोदरकीर्तनेन ।
माद्रीसुतौ कथयतां न भवन्ति रोगाः॥ २
As for the BORI Critical Edition, although it does begin with nārāyaṇaṃ namaskṛtya..., the verse is not numbered (it's the 0th verse).
01001000a nārāyaṇaṁ namaskr̥tya naraṁ caiva narottamam
01001000c devīṁ sarasvatīṁ caiva tato jayam udīrayet
01001001A lomaharṣaṇaputra ugraśravāḥ sūtaḥ paurāṇiko naimiṣāraṇye śaunakasya kulapater dvādaśavārṣike satre
01001002a samāsīnān abhyagacchad brahmarṣīn saṁśitavratān
01001002c vinayāvanato bhūtvā kadā cit sūtanandanaḥ
In his paper Epic Studies, V. S. Sukthankar explains the reason for including the opening stanza in the CE and yet not numbering it:
Type No. 2 (N ≠ S). I agree with R. [Dr. Ruben] that when there is a conflict between N and S and they stand opposite to each other with two divergent readings, no definite decision is, in general, possible as to which is the original; the versions should a priori be placed on an equal footing and treated with impartiality. Accordingly, in such cases, I have adopted as stop-gap the reading of N, placing a wavy line below it, to show that the reading is uncertain. R. mentions an exception to this procedure of mine, but the exception is only apparent. R. has failed to understand my motives in departing from my usual practice in the solitary instance of the benedictory stanza with which the epic begins (Nārāyaṇaṃ namaskṛtya etc.). I have printed it above the line not because it is found in K0 I or in K or even in N, but simply as a maṅgala, I am aware that the stanza is missing in S. There is, therefore, every probability that it did not belong to the archetype. I am also fully aware that the stanza is a characteristic mark of the works of the Bhāgavata sect and not peculiar to the Mahābhārata. There is, however, the fact that all our MSS. of the Ādiparvan begin with some benedictory stanza. These stanzas have probably usurped now the place of some simpler maṅgala with which the epic once began.
No orthodox Hindu work can begin without a maṅgala; and this edition of the Mahābhārata, critical though it be, is and remains a Hindu work which could not dispense with a maṅgala.
My recognition of the unoriginal character of the stanza is, however, clearly implied by the fact that I have omitted to give the stanza a number, differing in this respect conspicuously from the earlier editions, which treat it as the first stanza of the epic and an integral part of the text.
In Gita Press edition of Mahabharata, Adi Parva, 1st Chapter, 42nd verse is translated thus,
मन्वादि भारतम केचिदास्तीकीआदि तथा परे | तथोपरिचाराद्यन्ये विप्र: सम्यगधीयते ||
कोई कोई इस ग्रन्थका आरम्भ 'नारायण नमस्कृत्यं ' से मानते हैं और कोई कोई आस्तिक पर्व से | दूसरे विद्वान ब्राह्मण उपरिचर वसुकी कथा से इसका विधिपूर्वक पाठ प्रारम्भ करते हैं |
Nārayaṇa Namașkṛtyam verse is indeed bona fide.