As for your first question, you're right in pointing out that, given the context, one would expect something like "(...) necesse primum [ex quo corrupto aliquid factum est] non sempiternum esse", where the relative element quo would be a pronoun and its antecedent primum (singular neuter accusative, i.e. the subject of the infinitival clause) would be outside the relative clause. NB: as pointed out by TKR (see the comment below), Aristotle is talking about primum/τὸ πρῶτον in a technical sense.
Why don't we find this expected structure here? I don't know. Given that the context seems to exclude the quasi-adverbial reading of primo modifying corrupto (see the comments below), which would be associated to the (quite different!) interpretation "[that: elliptical antecedent id] from which being first corrupted something came" (e.g., cf. Reeve's translation in bold above), the only remaining possibility turns out to be the following one, which is based on the incorporated antecedent analysis. As pointed out by A&G § 307b, p.186, it is typical of Latin (but not of English) that "the antecedent noun may [also] appear only in the relative clause, agreeing with the relative in case". Assuming this analysis, in the sentence at issue here, the "antecedent" primo is inside the relative clause and agrees with the relative quo in case (ablative). In this sentence quo is not a pronoun but rather an adjective modifying the substantivized category expressed by primo (again, recall that primum/τὸ πρῶτον is used in a technical sense here). This said, I do think that this particular sentence of Medieval Latin can be said to be a bit forced or unnatural (at least in Classical Latin).
As for your second question, to the extent that the so-called "dominant participle construction" (e.g. ab urbe condita) often sounds more natural/idiomatic than its corresponding verbal nominalization (cf. ab urbis conditione), you are right when claiming that ex quo corrupto can be preferred over ex cuius corruptione. Since you are looking for some references, my initial suggestion is that you could take a look at this recent work by Olga Spevak (2018):
Spevak, Olga (2018). "La construction à participe dominant vs. le nom verbal chez Cicéron". Revue de Philologie 92 (1): 63-84.
If you cannot read French, some brief remarks on the parallelism between eventive nouns and dominant participles are also included in Pinkster's (2021: 27-28) second volume of his monumental Oxford Latin Syntax. For instance, as pointed out by him, note that the following example from Tacitus can be paraphrased through an eventive noun: occisio dictatoris.
Cum occisus dictator (...) pulcherrimum facinus videretur (Tac. Ann. 1.8.6)
Pinkster, Harm (2021). The Oxford Latin Syntax. The Complex Sentence and Discourse. Oxford: OUP.
If you're interested in "dominant participle constructions", you can also find some discussion in previous posts like the following ones: e.g., see here and here, inter alia.
NB: The works above by Spevak and Pinkster are quite descriptive, whereby I think they are quite readable. In case you are also interested in more technical/fine-grained analyses of "dominant participle constructions", please let me know and I will provide you with some additional references.