I have come to realize that in all the European languages I know of, the modal verbs change the verb they control to the infinitive form. These languages are all case-based (Spanish, Danish, English, German, etc.) and all follow the same rule, however not all languages follow this rule (i.e. Mandarin) so it must be a trait that has evolved somewhere along the branch of the case-based languages. Are there any case-based languages that do not follow this rule? and if not how far back in the evolution of language do you have to go to see the development of this trait?
Yes, there are plenty, for the simple reason that not all languages (even ones that have case) possess an infinitive.
All the examples you mention are fairly closely related Indo-European languages, more specifically ones from Western Europe. The fact that they all have this feature is not surprising.
I’m not sure I’d agree with your classification of ‘case-based languages’, though.
Firstly, the existence of case in a language says nothing about the origin or affiliation of that language – case is not a phylogenetic language feature. Cases exist in languages from completely unrelated families all over the world (e.g., Japanese, Greenlandic and ancient Sumerian all have cases, but are completely unrelated), and even closely related languages can differ in their case inventory (e.g., Irish and Welsh are both Insular Celtic languages and closely related, but where Irish has cases, Welsh does not).
Secondly, out of the four languages you mention as examples, three don’t actually have cases anymore, except in pronouns. So they’re hardly ‘case-based’. (And as a further example of the previous point, German, English and Danish are all closely related Germanic languages, but Danish and English have lost cases over the past millennium or so, while German has retained them.)
Moreover, even within Indo-European languages, and even within those that still do have fully-fledged case systems, there are languages that do not have an infinitive at all – indeed, avoidance or complete loss of the infinitive is one of the most famous features of the Balkan sprachbund.
Languages like Greek, Bulgarian, (Tosk) Albanian and Romanian all use various subjunctive-like structures instead of infinitives, some exclusively so, others optionally.
For example, the Greek way to say ‘I want to sleep; can you leave?’ (two infinitive constructions in English) is,
Θέλω να κοιμηθώ· μπωρείς να φύγεις;
I-want that I-sleep; you-can that you-leave?
– in which κοιμηθώ and φύγεις are the first and second person singular of what’s generally called the ‘dependent’ (formerly also ‘subjunctive’) form of the verbs κοιμάμαι ‘sleep’ and φεύγω ‘leave’, respectively.