MSVCRT.DLL has been an OS component since Win2000. But, as noted earlier, you never needed a CRT to write Win32 apps. Indeed, it was not uncommon especially in the 98/XP era for apps to be written directly against Win32 API (or with very thin wrappers like ATL and WTL; I did my share of that even as late as 00s). And even then pretty much all alternative toolchains, including C++ ones (notably, Borland C++), used their own runtimes anyway. The actual shared platform was always Win32, and there was never any sort of charge, direct or indirect, for using it.
The main reason why people shipped their own version of the CRT for VC++ was because they wanted to use a more modern version of VC++ itself (e.g. because of better support of new language features; C++ was just standardized then and all compilers were updating very rapidly to catch up), which then required a new version of the CRT that wouldn't be guaranteed by the lowest target OS version. But even VC++ did not require you to use the CRT; you could just #include <windows.h> and linker had a flag to drop stdlib.
And even when you wanted to use MSVCRT while targeting platforms where the desired version wasn't guaranteed, you still didn't have to ship it. All redistributable packages were (and are!) also published as standalone installers that users could just download and run themselves; indeed, it was not uncommon for open source Win32 software to require one to do exactly that. The bundling packages that MS also provided for integration with your own installer are a convenience, not a prerequisite.
The story with DirectX is very similar. DirectX did in fact ship as an OS component with every version of Windows starting with Win95 OSR2 and WinNT4. The reason why games pretty much always bundled it is because they wanted to use something newer, given how fast things changed back then. But, again, it was always available separately as a standalone installer, and any app that needed it could request it to be installed manually by the end user, and some apps did just that. I will also note that those standalone CRT and DirectX installers were also commonly redistributed, e.g. on large websites like Tucows.
With respect to Win32 APIs themselves being somehow protected through some form of IP, that wasn't the case, either. Again, Borland C++ / Builder used its own headers with no problem. And then of course pretty much every non-C toolchain that wanted to expose the dev to the OS API also had to provide their own equivalent of windows.h, which they all did - Delphi being probably the most prominent third party example, but there were numerous others - Ada, Eiffel etc; and even most scripting languages such as Perl. Again, back in that period, I myself wrote a bunch of Win32 header translations for then-nascent D. I don't recall anyone ever bringing up the notion that doing so was somehow legally risky; it was understood as an obvious and necessary step in development of any toolchain targeting the platform.
XP era also includes early .NET. The interesting thing about that one was that the .NET Framework redistributable (which, again, was provided as a standalone installer) also includes the C# and the VB command-line compilers, and since .NET metadata is embedded into the binaries, the result is that you effectively got a free build toolchain that let you do anything .NET could do. XP SP1 even included .NET 1.0 builtin, which I believe was the first time Windows came with dev tooling sufficient to write a full-fledged app for itself in the box.
The bit about "you never saw FOSS binary releases for Windows back then" is plainly not true. FOSS in general wasn't nearly as widespread then, and people who cared about it generally didn't care much for the DOS/Windows ecosystem, so mainline would often not even bother and just assume POSIX, and porting was a slow effort that required constant ongoing maintenance to keep up-to-date with upstream. But what did exist would normally be redistributed in binary form; examples include MinGW, Perl, and Python. Similarly, when using FOSS libraries like zlib, it was common to download and use redistributed prebuilt DLLs + import libs for your compiler.
So, to summarize: Microsoft never charged developers for access to the platform itself, and you could always write and distribute Windows apps without paying anything to MS. It charged the devs for tooling, but it also left the door wide open for alternative tooling, which did proliferate to the point where in some markets like Europe there was more Windows software written using Borland tools rather than Microsoft tools.