A.- Le 10 août 1998, l'Office fédéral des réfugiés a rejeté la seconde demande d'asile formée par X._, né en 1970, d'origine palestinienne, et sommé celui-ci de quitter la Suisse jusqu'au 30 septembre 1998 sous peine de refoulement. Par décision du 13 février 2000, le Service cantonal valaisan de l'état civil et des étrangers (ci-après: le Service cantonal) a ordonné la mise en détention immédiate en vue du refoulement de X._ pour une durée de trois mois au plus, en vertu de l'art. 13b al. 1 lettre c de la loi fédérale du 26 mars 1931 sur le séjour et l'établissement des étrangers (LSEE; RS 142. 20), des indices faisant craindre que l'intéressé entende se soustraire à son renvoi. Statuant le 17 février 2000, le Juge unique de la Cour de droit public du Tribunal cantonal du canton du Valais (ci-après: le Tribunal cantonal) a confirmé ce prononcé. Par arrêt du 28 mars 2000 (2A. 121/2000), le Tribunal fédéral a rejeté le recours formé par X._ contre ce jugement. B.- Le 25 avril 2000, le Service cantonal a requis la prolongation, pour six mois au plus, de la détention de l'intéressé, au motif que les autorités palestiniennes et israéliennes refusaient de fournir un document de voyage. Entendu le 10 mai 2000 par le Tribunal cantonal, X._ s'est opposé à l'admission de la requête et a conclu à sa libération immédiate. Persistant dans son refus de rentrer en Palestine, il a argué du caractère purement passif de sa résistance à l'exécution du renvoi. En outre, le Service cantonal échouait depuis au moins dix mois à obtenir un laissez-passer, que les autorités palestiniennes et israéliennes ne manifestaient nullement l'intention d'établir. L'exécution du renvoi s'avérait dès lors impossible, de sorte qu'il devait être libéré, conformément aux art. 13c al. 5 lettre a LSEE et 5 de la Convention européenne de sauvegarde des droits de l'homme et des libertés fondamentales du 4 novembre 1950 (CEDH; RS 0.101). Statuant le même jour, le Tribunal cantonal a confirmé le prononcé du Service cantonal. C.- Agissant le 8 juin 2000 par la voie du recours de droit administratif, X._ demande au Tribunal fédéral d'annuler l'arrêt rendu le 10 mai 2000 par le Tribunal cantonal et de le libérer. Le Tribunal cantonal renonce à se déterminer. Le Service cantonal propose de rejeter le recours. X._ ne s'est pas exprimé sur cette réponse. L'Office fédéral des étrangers n'a pas déposé d'observations mais, sur invitation du Département fédéral de justice et police, l'Office fédéral des réfugiés a exposé par courrier du 21 juin 2000 les difficultés auxquelles se heurtait le renvoi des personnes d'origine palestinienne et les démarches effectuées en vue de les résoudre. 