Anime about a girl who could see a kingdom up in the clouds that only she could see

Question

Back in my early teens, I discovered this anime about a girl who could see a kingdom up in the clouds that only she could see. She would try to ignore it and definitely wouldn't talk about it to anyone so she wouldn't come off as weird or strange to her friends from school.

I'm not too sure about the plot since I've only seen like, an episode or two, but I know that the king of this kingdom in the clouds had fiery red hair (at least I think he was the King, can't fully remember). The girl starts having vividly clear visions of the man with the red hair. These visions began to disturb her seemingly normal life, she couldn't understand why she was seeing him or how.

Eventually, one night in her room, her visions become a direct link to him and they are now able to communicate. This mystery man is as confused as her as to why they're connected and seems mildly annoyed by it. If I can remember correctly, he was busy fighting for his kingdom (or for other reasons) and had better things to do than talking to her.

This, sadly is all I can remember. I know the details are vague, and could possibly be a bit off, but the memory of this particular anime has stuck with me through the years. Unfortunately, I wasn't smart enough to try to remember the name or even thought about writing the name down. It bothers me so much that I couldn't find this anime again to finally finish watching it.

Does it sound familiar to any of you? If you happen to know what anime this is please let me know, I would greatly appreciate it!

☆UPDATE☆

After finding a way to watch Munto, I can tell how off my memory was on the details I described. But either way, I am so happy to finally be able to watch this show/movie again. I'm almost done watching it and it's better than I remember. Shout out @LogicDictates for finally ending my search. I'm so very grateful ❤

Answer 1

This is Munto (2003).

From MyAnimeList:

Above Earth, invisible to humans, float the Heavens—a collection of floating island kingdoms supported by the magic of their godlike inhabitants. The mysterious power source known as Akuto enables this magic to exist, but this is quickly running out. In response to this energy crisis, most of the kingdoms in the Heavens agree to use the minimum amount of Akuto required to sustain themselves, except for the Magical Kingdom. The leader of this kingdom, the Magical King Munto, believes that Akuto can be replenished if he travels to Earth and meets a mysterious girl shown to him by a seer. While Munto sets off on the dangerous journey, the other kingdoms attempt to destroy the Magical Kingdom and acquire the remaining Akuto for themselves.

On Earth, Yumemi Hidaka is dealing with her own problems. She can see floating islands in the sky that nobody else can. While her best friend Ichiko Ono believes her, Yumemi wonders if she is going insane. When Munto suddenly appears before her, Yumemi dismisses him as a mere delusion. She is more concerned about her 13-year-old friend Suzume Imamura, who is attempting to elope with her delinquent boyfriend. As the Magical Kingdom nears the point where it will fall from the sky, Munto's quest to save both the Heavens and Earth grows increasingly desperate.

The plot summary above is for the two-part original video animation (OVA), which was released in 2003. The story was also adapted into a TV series -- titled Sora wo Miageru Shoujo no Hitomi ni Utsuru Sekai or Munto TV -- released in 2009.

To save both the Magical Kingdom and the Heavens and restore the flow of akuto, the flow of energy of everything, the Magical King Munto must follow a vision and find the girl Yumemi in the normal world. Yumemi herself is just a normal girl except that she is the only one who can see the islands of the Heavens floating above. When Munto appears before her she starts thinking about hers and others responsibility to the world.

According to the character profiles on MyAnimeList, the main character is Yumemi Hidaka -- a schoolgirl with brown hair, as you described -- and King Munto does indeed have fiery red hair.

Answer 2

LogicDictates already gave Munto as an answer but I might add there is another anime that fits the description namely Sora o Miageru Shoujo no Hitomi ni Utsuru Sekai (2009). Its protagonists are also named Munto and Yumemi so it might be some kind of remake of Munto.