Thanks to A LOT of trial and error and A LOT of help from Janne Mikkonen we were able to destroy this bug!
Somehow, the combonation of a Win2003 IIS6 server and PHP 4.3.9 created this error. When we upgraded to PHP5 the problem was gone.
What was frustrating was that I know that there are plenty of PHP 4.3.9 users out there using Moodle and having no problems. But anyway, we're EXTATIC to not have to deal with the hundreds of student questions and complaints anymore (for that issue at least!)
Thanks to the MOODLE DISCUSSION FORUMS!! It's really a great service!