There are comments in the remez.cc source code that indicate that there may be some issues, specifically with the Search() routine. For example, near the top:
/**************************************************************************
* There appear to be some problems with the routine Search. See comments
* therein [search for PAK:]. I haven't looked closely at the rest
* of the code---it may also have some problems.
*************************************************************************/
and in the Search routine itself:
// PAK: we sometimes get too many extremal frequencies