CX>Приведи минимальный код, на котором проявляется ошибка. Думается, баг будет быстро найден.

bool process_data(SOCKET sock)
{
    /////////////////
        if ((received = recv(sock, buf, RECVBUFSIZ, 0)) != SOCKET_ERROR && received>2) {
      // здесь вот buf может являться тем злополучным сообщением (а может и не быть им).
      buf[received] = '\0';
            pushToStack(buf,received); // тут просто парсером прогоняю сообщение и кладу в стек сообщений
            return true;
    }
    return false;
}

/////////////////////////////////////////////////////////////////////////////
UINT ListenSockets(LPVOID lpvoid)
{
    while (true) {
            ///////////
        if ((accepted = accept(ssocket, (struct sockaddr *) &ca, (socklen_t *)&cal)) != SOCKET_ERROR){
                    int size=sizeof(sockaddr);
                    sockaddr_in adr;
                    int ret=getpeername(accepted,(sockaddr*)&adr,&size);
                    if(adr.sin_addr.S_un.S_addr==IP_CLIENT){
                if(clients.size()==0){
                    sprintf(buffer,"Client connected [%s]",inet_ntoa(adr.sin_addr));
                    clients.push_back(accepted);
                }else{
                    sprintf(buffer,"Client already connected [%s]. Ignored",inet_ntoa(adr.sin_addr));
                    shutdown_socket(&accepted);
                }
            }else{
                sprintf(buffer,"Illegal client want to connect [%s]",inet_ntoa(adr.sin_addr));
                shutdown_socket(&accepted);
            }
            toLog(buffer);
        }
        
        // Preparing descriptor sets
        FD_ZERO(&readfds);
        FD_ZERO(&exfds);
        FD_SET(ssocket, &exfds);
        tv.tv_sec = 1;
        tv.tv_usec = 0;
        maxfd = ssocket;

        for (CL::iterator ii = clients.begin(); ii != clients.end(); ++ii) {
            FD_SET((SOCKET )*ii, &readfds);
            FD_SET((SOCKET )*ii, &exfds);
            maxfd = max(maxfd, (SOCKET )*ii);
        }
    
        // select failing breaks the work
        if (select(maxfd + 1, &readfds, NULL, &exfds, &tv) == -1) break;
        
         // On exception in server socket also breaks immediately
        if(FD_ISSET(ssocket, &exfds)) break;
    
        // Test events on client sockets
        for (ii = clients.begin(); ii != clients.end(); ++ii) {
            if (FD_ISSET(*ii, &exfds)) {
                                toLog("Client exception");
                if (*ii != INVALID_SOCKET) shutdown_socket(&(*ii));
                if ((ii = clients.erase(ii)) == clients.end()) break;
            }
            if (FD_ISSET(*ii, &readfds) && !process_data(*ii)) {
                                toLog("Failed to read client");
                if (*ii != INVALID_SOCKET) shutdown_socket(&(*ii));
                if ((ii = clients.erase(ii)) == clients.end()) break;
            }
        }
    }
    for (CL::iterator ii = clients.begin(); ii != clients.end(); ++ii) {
        if (*ii != INVALID_SOCKET) shutdown_socket(&(*ii));
        if ((ii = clients.erase(ii)) == clients.end()) break;
    }
    /////////////////
  shutdown_socket(&ssocket);
    /////////////////
}

            if (FD_ISSET(*ii, &readfds) && !process_data(*ii)) {
                                toLog("Failed to read client");
                if (*ii != INVALID_SOCKET) shutdown_socket(&(*ii));
                if ((ii = clients.erase(ii)) == clients.end()) break;
            }

bool process_data(SOCKET sock)
{
    int received = 0, required = 2;
    while((received = recv(sock, buf + received, required - received, 0)) > 0);
    if(received == SOCKET_ERROR) return false;

    // Тут нужно особое внимание обратить на byte order. Если у тебя архитектура little-endian,
    // а значение высылается в сетевом порядке байт, то ntohs обязательна
    // short здесь в предположении что sizeof(short) == 2
    short size = ntohs(*reinterpret_cast<short *>(buf));
    
    required = size;
    received = 0;
    while((received = recv(sock, buf + received, required - received, 0)) > 0);
    if(received == SOCKET_ERROR) return false;
    
    buf[size] = '\0';
    pushToStack(buf, size);
    return true;
}

bool process_data(SOCKET sock)
{
    int received = 0, required = 2;
    while((received = recv(sock, buf + received, required - received, 0)) > 0);
    if(received == SOCKET_ERROR) return false;
    short size = ntohs(*reinterpret_cast<short *>(buf));
    
    required = size;
    received = 0;
    
        
        while((received = recv(sock, buf + received, required - received, 0)) > 0);
    if(received == SOCKET_ERROR) return false;
    
    
        buf[size] = '\0';
    pushToStack(buf, size);
    return true;
}

Первые два    Оставшаяся часть
байта             сообщения
    |                 |
+--------+------------------------+
| xx  xx | xx  xx  xx  xx  xx  xx |
+--------+------------------------+

C>bool process_data(SOCKET sock)
C>{
C>    int received = 0, required = 2;
C>    while((received = recv(sock, buf + received, required - received, 0)) > 0);
C>    if(received == SOCKET_ERROR) return false;
C>    short size = ntohs(*reinterpret_cast<short *>(buf));
    
C>    required = size;
C>    received = 0;
    
C>        
C>        while((received = recv(sock, buf + received, required - received, 0)) > 0);
C>    if(received == SOCKET_ERROR) return false;
C>    
    
C>        buf[size] = '\0';
C>    pushToStack(buf, size);
C>    return true;
C>}

C>