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”.