If the offending characters are from a language other than English but one Microsoft supports, you can install the relevant MUI (Multilingual User Interface) language pack from Windows Update, or the relevant LIP (Language Interface Pack) from here as a possible fix.
In addition to the above, you may also need to change the System Locale.
The system locale determines the default character set (letters,
symbols, and numbers) and font used to enter and display information
in programs that don't use Unicode. This allows non-Unicode programs
to run on your computer using the specified language. You might need
to change the default system locale when you install additional
display languages on your computer. Selecting a different language for
the system locale doesn't affect the language in menus and dialog
boxes for Windows or other programs that do use Unicode.
To do so:
Type "region" in the Start Menu search box (without the quotes)
Open the Region and Language Control Panel applet
Click the Administrative tab, and then, under Language for non-Unicode programs, click Change system locale. If you are prompted for an administrator password or confirmation, type the password or provide confirmation.
Select the language, and then click OK.
If you're prompted to restart your computer, click Restart now to do so.
However, if the offending characters are something like ™ as mentioned above, I do not believe there's any official Microsoft fix for this zipfldr.dll limitation, that has existed as long as Windows has had this feature (so if you really did fix it earlier, possibly you installed some third party component). From Wikipedia:
Versions of Microsoft Windows have included support for zip
compression in Explorer since the Plus! pack was released for Windows
98. Microsoft calls this feature "Compressed Folders". Not all zip features are supported by the Windows Compressed Folders capability.
For example, AES Encryption, split or spanned archives, and Unicode
entry encoding are not known to be readable or writable by the
Compressed Folders feature in Windows XP or later versions.
The ZIP file format lacked Unicde support for a long time, and this extension was only added 6 years ago in 2006. As per APPENDIX D - Language Encoding (EFS) of the ZIP File Format Specification:
D.1 The ZIP format has historically supported only the original IBM PC
character encoding set, commonly referred to as IBM Code Page 437.
This limits storing file name characters to only those within the
original MS-DOS range of values and does not properly support file
names in other character encodings, or languages. To address this
limitation, this specification will support the following change.
[Read document for the rest.]
Since then of course all of the major Windows archivers implementing the format have been updated to include Unicode support, beginning I believe with WinZip in 2008. Unfortunately, Microsoft for some strange reason licensed a third party library for its Compressed Folders feature (although it's not terribly tough to code ZIP support), and obviously this library pre-dates the addition of Unicode to the ZIP file format. Also, as a clear sign of just how much it cares for this feature, Microsoft has not updated the code to fix this bug till date (apparently, even the new System.IO.ZipArchive class in the latest version of the .Net Framework i.e. 4.5 did not get this right initially, but the bug has since been fixed). I guess they expect everyone to install one of the many full-featured third party archivers available, which is precisely what I recommended to you as well above.
You can read the sordid details about this peculiar lack of Unicode support in Windows in the following series of blog posts by Microsoft's Michael Kaplan:
P.S. "I just found out that zipping with windows' "send to" works as good as Winrar's "best" zipping, but so much faster." - I just tested this, multiple times. Other than the extra time taken to open WinRAR's Add to archive dialog, select ZIP as the archive format and press OK, the actual time taken for compression was roughly the same for both, with WinRAR taking less time in general (albeit the differences were negligible). If you saw a huge difference, it could only have been if you tested WinRAR on a set of files first, then immediately compressed the same files with Compressed Folders. Naturally the second time around Windows had already cached the data, so the process took a fraction of the time it did initially. Do it in the opposite order on a set of files you haven't touched earlier during the current Windows session, and I bet the result will be reversed. :)
As for the final compressed size, depending on the data/combination of file formats archived, I found either of the two doing a better job (although again the differences were negligible). Of course, the 7z or Rar (or even WinZip's ZipX) formats are far better in this regard and will beat plain ol' ZIP almost any day (i.e. ZIP using the traditional/legacy deflate algorithm instead of PPMd and the like).