I'm not an admin, just a site owner, so I don't know when we got our last update. However, it appears to have just arrived in our tenant, since I'm in the middle of creating a set of training pages and this behavior magically appeared when I came back from lunch and created a new page - it didn't happen earlier today.
From your notes above and my testing (to confirm that I'm seeing the same thing), it appears that the CSS is applied to the text web part when it's created, because I can edit existing text web parts with the old behavior, but a new page created from that page puts the text in a web part without paragraph spacing. On that theory, I am proceeding to create pages and manually inserting blank lines between paragraphs. If this hypothesis about when the CSS is applied is correct, then these pages should still look OK when (if) Microsoft fixes this breakage.
TBH I'm hoping that they're planning to make paragraph spacing configurable and simply forgot to add the UI element to control it. Probably a vain hope...