A free option, although one that will require a little
download time, is to use OpenOffice (
http://www.openoffice.org/), a free office suite that includes word processing, spreadsheet and other modules similar to those offered by Microsoft.
OpenOffice can be used in two ways to overcome your problem. The first, and most straightforward, is to copy the content of your Word document and paste it into OpenOffice. It will retain all of the formatting, and when you then copy and paste the text from OpenOffice into Moodle the Word rubbish is gone.
The other way, for new documents, is to actually create the text in OpenOffice and copy and paste it straight into Moodle. You can then save the OpenOffice document into Word (.doc) format using "Save as ...", so that you still end up with your Word document if need be - and it sounds like that's important in your institutional setting.
This may seem a bit unwieldy in the short term, but in the long run, if Clean Word HTML is not working, it does offer a reasonable and cheap solution to a painful problem.
For the record, this also works using Apple's Pages, for those of you who use Macs.