How did Galadriel knew that Gandalf was back?

[Nilpaurion Felagund]

...but mortal men and Ainur who died left the world entirely.

So that's what happens to dead Ainur...

Anyway...yes, they could communicate without the Rings. Else they could talk about Celeborn without his knowledge, and, as Legolas pointed out, he was part of the conversation.

One more thing: Arwen does it.

Arwen remained in Rivendell...from afar she watched over him in thought;

(LotR, Appendix A, II, v)

Galadriel's inability to perceive Gandalf could be due to the following reasons:

• He could already be dead(most likely).
  
• His will is actively engaged by his Maiarin foe. *Galadriel gets the answering machine from Gandalf's line*
  
• His connection was cut off, and he had no cash to pay up.

But that is not the question.

How did Galadriel knew that Gandalf was back?

Simple...connection reestablished.

<font size=1 color=339966>[ 1:41 AM December 11, 2003: Message edited by: Nilpaurion Felagund ]