Why didn't Voldemort begin searching for the Elder Wand much earlier on?

Question

After experiencing Priori Incantatem in the graveyard during Goblet of Fire (and not coming off the best for it) Voldemort must have clocked that a) Harry and he had some sort of wand connection and that b) if he was to defeat Harry that he'd have to find a new wand. He certainly knew as much in Deathly Hallows. But the situation hadn't changed in the last two years - he needed to solve the wand problem during Order and Prince as well, but didn't.

The Elder Wand would presumably have held as much of an appeal to him in Order of the Pheonix as it did during Deathly Hallows. If he knew he needed a new wand then that wand would've been an attraction. True, Dumbledore still had the wand at this point. But Voldemort didn't know that and would still have had to pursue the trail of the wand through Gregorovitch and Grindelwald.

Alternatively, he could've settled for a totally separate, brand new wand. He could've taken Ollivander a year or so earlier to get a wand that would defeat Harry.

I appreciate that Voldemort was trying to get hold of the prophecy that year but a supervillain can have more than one evil plan on the go simultaneously, can he not?

Why didn't Voldemort take action to pursue the Elder Wand in the immediate weeks and months after Harry escaped in Little Hangleton?

Answer 1

He did not understand what had happened

First, Voldemort did not understand the reason for his and Harry's wands connecting until Ollivander told him under torture:

“He wanted you to tell him how to overcome the connection between our wands,” said Harry.

Ollivander looked terrified.

“He tortured me, you must understand that! The Cruciatus Curse, I-I had no choice but to tell him what I knew, what I guessed!”

“I understand,” said Harry. “You told him about the twin cores? You said he just had to borrow another wizard’s wand?”

—Harry Potter and the Deathly Hallows

Dumbledore understood immediately, yes, but it has always been clear that Dumbledore understands far more of most sorts of magic than Lord Voldemort. Voldemort did not know whether it was some power that Harry possessed (perhaps as a result of his mother's sacrifice), some connection between their wands, or something else altogether. He was not about to throw away his wand, which he had been bonding with for decades, over one guess among many.

After this, he sought to borrow Lucius's wand. It was only once this course of action still (apparently) failed to overcome the bond between him and Harry that he realized he needed a different strategy.

“We were talking about the other wand, the wand that changes hands by murder. When You-Know-Who realized my wand had done something strange, he came back and asked about that other wand, didn’t he?”

“How do you know this?”

Harry did not answer.

“Yes, he asked,” whispered Ollivander. “He wanted to know everything I could tell him about the wand variously known as the Deathstick, the Wand of Destiny, or the Elder Wand."

—Harry Potter and the Deathly Hallows

---

Why would he not have sought the Elder Wand earlier, even before he believed he needed it to kill Harry?

1. Priorities. Voldemort had many other things he needed to do, and getting the Elder Wand may not have been high on his list.

2. Knowledge. Voldemort did not know where to start looking for the Elder Wand until Ollivander told him.

   “Mr. Ollivander,” said Harry, “you told You-Know-Who that Gregorovitch had the Elder Wand, didn’t you?”

   —Harry Potter and the Deathly Hallows

3. Arrogance. Voldemort has always been surpassingly confident in his own power, believing that he needs little more than tools with which to channel it. He sought the Elder Wand only out of necessity:

   "The Dark Lord,” said Ollivander in hushed and frightened tones, “had

   always been happy with the wand I made him—yew and phoenix feather, thirteen-and-a-half inches—until he discovered the connection of the twin cores. Now he seeks another, more powerful wand, as the only way to conquer yours.”

   —Harry Potter and the Deathly Hallows

   As Dumbledore explained, Voldemort was contemptuous of having to rely on anything external¹ to himself. He would not have liked the idea that a good portion of his achievements could be attributed to anything besides his own magical skill:

   "Voldemort likes to operate alone, remember. I believe that he would have found the thought of being dependent, even on the Elixir, intolerable. Of course he was prepared to drink it if it would take him out of the horrible part-life to which he was condemned after attacking you, but only to regain a body. Thereafter, I am convinced, he intended to continue to rely on his Horcruxes."

   —Harry Potter and the Half-Blood Prince

   Of course, eventually he got over this, once he decided that the Elder Wand would make him invincible.

   ^{1: Since the Horcruxes were simply pieces of his own soul, he probably did not think of them this way.}

Answer 2

He assumed he could work around it by using a different wand.

Admittedly, Dumbledore was his first priority. It's not like he took two years to hunt for a new wand, he took two years to both build up his power and find a way to remove Dumbledore. The prophecy that Harry would defeat him was a priority, but practically facing off against an under experienced teenage wizard wasn't some major concern of his.

Or at least, up until he tried to, when Harry was evacuated from the Dursleys. He was using Malfoys wand at the time, and was caught completely by surprise when there was a similar wand conflict. It wasn't until that point that he became convinced that he needed a far better wand to overcome that link, as he proved he couldn't simply circumvent it. Thus the start of the search for the Elder Wand.