protagonist is stuck together with a supernatural or fantasy person

[libba]

I'm looking for a story where the protagonist suddenly comes across some supernatural or fantasy person, and now they are stuck together so adventure begins because of it.

Maybe the protagonist accidentally summons the person, or frees him or her. Maybe there is a darker motive at work. But whatever it is, they can't be separated now for some reason, that's the rule of the game.
But it's not "they randomly met and then went on together", the very fact of their union means something plot-wise, it's important, there is a hidden meaning.

Best examples: Rozen Maiden, Fate/Stay Night, Pandora Hearts, Shakugan no Shana.
Here their union is something that's the very foundation of the plot.

Other examples: Monochrome Factor, Kuroshitsuji (technically Ciel did just that), InuYasha (in a way).

Not quite what I want but might be mistaken for that and I've watched it anyway: Bleach, Shingetsutan Tsukihime, Shikabane Hime, Hikaru no Go, Durarara!, Zero no Tsukaima.

[Irenicus]

Yumekui Merry.

[Seishin]

Here's some you may look into:

Dance In The Vampire Bund

The main character in this one has connections to the Vampire Queen, but he was long since thought to be dead, having lost his memory in a former mission. Now the Vampire Queen has found him again, eager for him to fulfill his promise to protect her while she creates a nation for vampires to live alongside humans. If you don't mind ecchi and gore, you might enjoy this one.

Black Cat

Train Heartnet is the infamous gunman 'Black Cat', a cold-blooded assassin who works for the organization known as 'Chronos', bearing the mark XIII on his body. Most of his life was surrounded by violence, so Train is quiet, asocial and uncaring. However his life changes as he encounters the mysterious Sweeper (bounty hunter), Saya. Her unique way of living interested Train but tragedy occurs, resulting in Train changing the way he has lived towards the life of a Sweeper with newfound friends Sven and Eve.

Buso Renkin

The story begins when high school student Kazuki Muto is killed one night saving a mysterious girl from a monster, only to wake up in his school dorm, believing it to have been a dream. However, he soon finds out that dream wasn't a dream at all when a giant serpentine monster attacks him and his sister. Tokiko Tsumura, the girl he saved, explains that the monster is a homunculus. Kazuki had been attacked and killed by it when he was rescuing her. However, she, feeling responsible for him, revived him by placing a Kakugane medallion in his chest, serving as a replacement heart.

The Kakugane, as Tokiko explains, is an alchemical device that, when activated, takes a certain form based on the Kakugane's user, forming a unique Buso Renkin. The Buso Renkin is the only thing that can destroy a homunculus monster. Using this, Kazuki creates his own Buso Renkin (the "Sunlight Heart", a huge lance). Along with Tokiko and her own Buso Renkin (the "Valkyrie Skirt", an execution scythe), Kazuki joins the fight against the homunculi and their master.

[kitten320]

Katekyo Hitman Reborn!, Tsuna gets stuck with Reborn the proffesional mafiosi who becomes his teacher.

Kore wa Zombie Desu ka? Ayumu meets Yuu the necromancer and his life takes a great change. Series are ongoing but their meeting might be more than just meets the eye.

Yumekui Merry the main hero can see what everyone will dream about and eventually bumps into a girl from dreams with whom they make a bound.

Angel Beats

Claymore, I think Clare/Teresa arc fits well

Elfen Lied, at first glance two main heroes seem to be strangers to each other but their bonds go further than that... She also is searched for serial murderers.

[wingdarkness]

DeathNote - Invisible Shinigamis...Ryuk for the ultimate win...

XxXholic - Invisible spirits//sprites surround the main character at every turn...Lots of adventure in this one...

Hitman Reborn - The main cast of characters all have to train with baby-sized beings with awesome powers...The main baby (Reborn) is a miniature Lucky Luciano^^...

Heroman - Despite the clunky idea of the show (Boy with toy robot who transforms into uber-robo), I found it to be fairly awesome in it's overall action sequencing, and surprisingly satisfying to the end...Also first anime to make cockroaches as villains pretty cool..

[Kleo Scanti]

If you don't mind romance, try Ah! My Goddess!

[Kotohono]

I'll third Yumekui Merry and I think Omamori Himari might fit the type of series you want as well.

Or maybe Kami nomi zo Shiru Sekai[The World God Only Knows] as Keima inadvertently accepts a contract with a demon mistaking it for a challenge, and now must fulfill it, though it's romance, not action series .

[GreatTeacherKen]

Even though it's not really an adventure series and is more of a slice of life romantic comedy, Ah! My Goddess's premise perfectly fits the topic description.

[SeijiSensei]

I'll start by recommending Twelve Kingdoms. The tie between Yuuko and Keiki certainly fits your criteria that the bond be permanent and meaningful.

Here are a few less obvious suggestions. One is Nijuu Mensou no Musume. I'm not certain if Nijuu Mensou himself is "other-wordly" enough to qualify, though at times he seems superhuman. Otherwise his relationship with his "musume" Chizuko would fit your request.

Another suggestion is the fable based very loosely on Alice in Wonderland called Mahou Shoujotai Arusu (or the horrendous "Tweeny Witches" in R1). Young Alice, a human without supernatural abilities, loves magic because of its power to do good. She falls off a building and ends up in a world where magic truly exists, but its source requires the exploitation of magical beasts. After discovering that she, too, can perform magic in this world, she joins forces with two young witches to form a "magical girl squad" and cleanse the world of darkness.

[Edit: Re-reading that paragraph made me think that Kemono no Sou-ja Erin might qualify if you're willing to consider a show where a human girl befriends a magical beast. To say that this event has important implications for both of them would be an understatement.]

Finally, Ghost Hound might be a possible match. The main character survived a kidnapping when very young and now, at fourteen, seems capable of astral projection. His past brings him into contact with two other boys, and together they set out to uncover the true facts of the crime.

[Kotohono]

Originally Posted by SeijiSensei

I'll start by recommending Twelve Kingdoms. The tie between Yuuko and Keiki certainly fits your criteria that the bond be permanent and meaningful.

How did I let this one slip my mind when I was posting earlier? , Seconded .