Was meinst Du mit „anderer Server“?

[Raketenwilli]

...klingt das nach einer Ursache, die mit dem Code nicht unbedingt zu tun hat.

Den Eindruck habe ich auch, aber wo die zu suchen wäre?

OSI, Level 8. Ich würde den Fehler in Deinem eigenem Vorgehen, also Testaufbau, also Testgeschehen suchen.

Rolf hat das schon richtig beschrieben.

<?php
# Beim Testen immer aktivieren, auch da, wo Du den Cookie setzt:
error_reporting( E_ALL );
ini_set( 'display_errors', 1 );

# Beim Testen nicht über die eigenen Füße stolpern:
header( 'Expires: 0' );
header( 'Pragma: no-cache' );
header( 'Cache-Control: no-cache, must-revalidate' );

header( 'Content-Type: text/html' );
if( ! empty( $_COOKIE['Keks'] ) ) {
    echo '"Keks" ist da. Inhalt: "' . $_COOKIE['Keks'] . '"';
} else  {
    setcookie( 'Keks', date( 'Y-m-d H:i:s' ) );
    echo 'Keinen Keks empfangen. Hab ihn gesetzt. Drücke [F5]';
}

Und schau Dir bitte den Cookie auch im Browser und die gesendeten/empfangenen Header in den Entwicklertools des Browsers an.

Übrigens: Was meinst Du mit „anderer Server“?

Wenn Du auf einer Webseite von Server A das Cookie setzt, dann darf es gar nicht an einen Server B gesendet werden.