It sounds like you're not wiping the drive with Disk Utility before reinstalling?

I have been seeing this lately as well. Even off I do internet recovery over Ethernet and wipe the drive. Maybe I should change the partition to something other than APFS and then back? Seems like a lot of additional steps though.

I have a vague recollection from my days as a "Genius" that the last joined network is stored in NVRAM - could this be causing the issue?

I am definitely wiping the Macs. This issue seems prevalent with 10.14.3.

I have witnessed this too. It attempts to join our guest network even though our devices "should" be connection to our work SSID.

+1 for the auto guest network connection. It seems to happen if the ethernet adapter isn't detected immediately after the reboot (even though it remained connected during an erase & install of the OS). It's only happened once or twice, so not worth the time to troubleshoot at my org.

The following article discusses about blocking a open wireless network.

https://www.jamf.com/jamf-nation/feature-requests/3512/blocking-in-house-public-ssid-s-on-ios

We follow the above article to push a Configuration Profile with the 'enrollmentComplete' trigger to blacklist open wireless networks.