The problem was with the MSBuild version used by the workflows. I believe its SDKs are independant from the OS's SDKs, so it was not targeting the newer SDKs even though they are installed on the OS.

MSBuild is shipped with Visual Studio Built Tools 2022, which in our case was the outdated culprit.

Updating it allowed me to publish dotnet 8 apps via workflows successfully.

Thanks Jason Pan for the comment suggesting I do a version check from within the workflow. That revealed the missing SDKs.