Both versions (with and without the hyphen) are fine, meaning they both conform to common usage.

Incidentally, I assume “thousands of postmen and -women” is intended to avoid offending female postal employees. It may be well worth your time to discover whether it might have the reverse effect. This is a complex issue. See the question titled “[Gender-neutral Forms](https://english.stackexchange.com/questions/76147/gender-neutral-forms)”.