When did Dumbledore correspond with Aunt Petunia?

Question

Consider the following quote:

'Albus Dumbledore,' said Dumbledore, when Uncle Vernon failed to affect an introduction. 'We have corresponded, of course.' Harry thought this an odd way of reminding Aunt Petunia that he had once sent her an exploding letter, but Aunt Petunia did not challenge the term..
_{Will and Won't, Half-Blood Prince}

My thoughts

I always took this highlighted part of the quote at face value, and assumed that Dumbledore was, in his inimitable style, referring to the Howler and Aunt Petunia was just too shocked and scared to say anything (after all, she was speaking to a wizard, and one who was eccentric enough to dress in complete wizard outfit at that.)

An alternative explanation

However, I've come across a new explanation from another Potterhead that states that Dumbledore was actually referring to

the fact that he and Petunia had corresponded way back, when Petunia was just a kid, and had written to Dumbledore, asking to be allowed to study in Hogwarts, and received his reply denying her admission.

Again, it may be that Petunia was just too flabbergasted to speak, but what differs is the correspondence Dumbledore was referring to.

My Questions

• So, which of the explanations is correct? The first? The second? Or both? Or something else? What the 'correspondence' Dumbledore referred to?

• And did Dumbledore correspond with Aunt Petunia anytime else?

Note 1.: I'm referring to Dumbledore corresponding​ with Petunia alone, not the Dursleys together. He might have corresponded with the Dursleys together a couple of times.

Note 2.: As part of this, I've not counted the letter Dumbledore wrote to the Dursleys explaining why Harry had to be left with them. Nor the letter explaining their severe breach of school rules by flying the Ford Anglia.

Note 3.: Please use only canon sources and back up your answers with evidence.

My research

In searching for communication between Dumbledore and Petunia, I came across this answer

but that doesn't specifically answer my question.

Answer 1

It likely means the letter he left with Harry saying to keep him, or just that he's talked to her.

I see in your question, Note 1 excludes any correspondence that might be to both of the Dursleys. But I'm fairly sure that the letter Dumbledore is referring to is the one where he tells them they need to keep Harry. The Howler arrives right after Uncle Vernon seriously tries to kick Harry out of their house.

An awful voice filled the kitchen, echoing in the confined space, issuing from the burning letter on the table.

"Remember my last, Petunia." Aunt Petunia looked as though she might faint. She sank into the chair beside Dudley, her face in her hands. The remains of the envelope smoldered into ash in the silence. - Harry Potter and the Order of the Phoenix, Chapter 2 (A Peck of Owls)*

It seems very likely that the "last" Dumbledore was referring to was his letter about Lily's death, and explaining that they needed to keep Harry. Just by saying "remember my last" the Howler gets Petunia to make Vernon let Harry stay with them.

“The boy – the boy will have to stay, Vernon,’ she said weakly.

‘W-what?’

‘He stays,’ she said. She was not looking at Harry. She got to her feet again.

‘He … but Petunia …”- Harry Potter and the Order of the Phoenix, Chapter 2 (A Peck of Owls)*

In intent, the Howler and the letter with Harry mean the same thing - she has to keep Harry.

If Dumbledore meant to remind her of either the Howler or the letter he left with Harry on the Dursleys' doorstep, the intention would have been the same, to subtly remind her that she can't let Harry be kicked out of the house. The entire reason for a Howler saying "remember my last" was to remind her of what he said about keeping Harry in that letter.

While it's unclear who exactly the letter Dumbledore left with Harry was addressed to, the Howler reminding of it was addressed to only Petunia. In addition, that letter he left with Harry would have, even if it was addressed to both Dursleys, been more for Petunia than Vernon. It was her presence that created the protection, her sister that died, and she also had more of an understanding of the magical world than Vernon did.

But Dumbledore might just mean that he's not that unfamiliar of a figure in her life.

The reason that Dumbledore arrived at the Dursleys' house was to collect Harry and make sure that Harry had inherited Number 12 Grimmauld Place. This context doesn't seem to point to a specific letter.

However, Dumbledore mentioned that they have corresponded instead of an introduction, as a way of identifying himself to Petunia. It could be Dumbledore's way of reminding Petunia that she has to keep Harry, or it could simply be reminding her that, although his presence in her house is unusual, she has interacted with Dumbledore before and is at least somewhat familiar with him.

“Ah, and this must be Petunia.’

The kitchen door had opened, and there stood Harry’s aunt, wearing rubber gloves and a housecoat over her nightdress, clearly halfway through her usual pre-bedtime wipe-down of all the kitchen surfaces. Her rather horsy face registered nothing but shock.

‘Albus Dumbledore,’ said Dumbledore, when Uncle Vernon failed to effect an introduction. ‘We have corresponded, of course.” - Harry Potter and the Half-Blood Prince, Chapter 3 (Will and Won't)

It's unlikely he meant only the letter he sent her about if she could attend Hogwarts.

I'm fairly sure he wasn't referring to only the letter he sent her about being allowed in Hogwarts when she was younger. In context, reminding her that she wrote him about if she could go to Hogwarts serves little purpose. Reminding her that they have to keep Harry is useful so that she'll make sure Harry stays, as she did after receiving the Howler. But in context, reminding her of the letter about her going to Hogwarts doesn't do anything useful.

Answer 2

What your first quote is referring to is the time where Dumbledore sends Petunia the Howler in Order of the Phoenix.

According to canon, Dumbledore corresponded with Petunia, alone, twice...

1. Before Lily went to Hogwarts

   “You didn’t think it was such a freak’s school when you wrote to the headmaster and begged him to take you.”
   Petunia turned scarlet.
   “Beg? I didn’t beg!”
   “I saw his reply. It was very kind.”

2. After the Dementor attack

   “Wait,” said Harry. “Wait a moment.”
   He sat up straighter in his chair, staring at Dumbledore.
   “You sent that Howler. You told her to remember — it was your voice —”
   “I thought,” said Dumbledore, inclining his head slightly, “that she might need reminding of the pact she had sealed by taking you. I suspected the dementor attack might have awoken her to the dangers of having you as a surrogate son.”

...and the only time where he sends her a Howler is in Order of the Phoenix.

It would have been absurd for Dumbledore to have sent a Howler to reply to Petunia's request of joining Hogwarts.

Howlers seem to be used only when the sender wants to convey a direct message to the recipient. In Ron Weasley's case this was to express Molly's disappointment in him. In Neville's case, it expressed his grandmother's disappointment with him. In Petunia's case it was to remind her how important it was to keep Harry.

Also, how could Lily have seen Petunia letter if it was a Howler? Surely it would have disintegrated, as a Howler does after it's read (or after it reads itself...). Therefore, it's without a doubt that Dumbledore was referring to the time (in Order of the Phoenix) where he sent Petunia the Howler to "Remember his last".

Answer 3

This is referring to this scene from The Order of the Pheonix:

Harry darted forwards to pick up the letter, but Aunt Petunia beat him to it.
"You can open it if you like," said Harry, "but I’ll hear what it says anyway. That’s a Howler."
"Let go of it, Petunia!" roared Uncle Vernon. "Don’t touch it, it could be dangerous!"
"It’s addressed to me," said Aunt Petunia in a shaking voice. "It’s addressed to me, Vernon, look! Mrs. Petunia Dursley, The Kitchen, Number Four, Privet Drive –"
She caught her breath, horrified. The red envelope had begun to smoke. "Open it!" Harry urged her. "Get it over with! It’ll happen anyway."
"No."
Aunt Petunia’s hand was trembling. She looked wildly around the kitchen as though looking for an escape route, but too late – the envelope burst into flames. Aunt Petunia screamed and dropped it.
An awful voice filled the kitchen, echoing in the confined space, issuing from the burning letter on the table.
"Remember my last, Petunia."
Aunt Petunia looked as though she might faint. She sank into the chair beside Dudley, her face in her hands. The remains of the envelope smoldered into ash in the silence.
_{Harry Potter and the Order of the Pheonix, chapter 1}

It also could be referring to the letters that Petunia wrote asking to be accepted into Hogwarts ("You didn't think it was such a freak's school when you wrote to the Headmaster and begged him to take you."), but I don't think so.

And Harry at least seems to think that it's talking about the Howler that was sent, and since we see the series from his PoV, I'll accept his opinion ;)