I have looked at the HKLM/Software/Microsoft/WindowsNT/CurrentVersion/WinLogon/LegalNotice registry keys, but that puts up a separate window (which the users then have to click on OK button for).
I have also looked at Logon Studio, but got really, REALLY lost in what that was trying to do.
It also seems to want to work by modifying the "Welcome screen", which I'm not using (connected to a domain controller).
I'm sure others have had to do this before