I'm going to assume that the lesser nobodies still don't have hearts, but the more advanced ones do and will grow ones due to being able to remember thier past lives
From what I understood even "advanced" Nobodies and/or human-shaped ones start out with no heart at all. The notion that Nobodies do not have hearts was never contradicted. We only gained additional information now that under certain circumstances some Nobodies can give birth to a new heart and this one can be nutured and given form over time until it may become a fully fledged heart.
Xemnas explains it this way and Ansem the Wise actually confirms it when speaking with Riku later on:
Ansem the Wise said:
Ansem the Wise: That's right. Maybe it will be a clue for you all, to bring back your lost allies. The heart is something that can be born, and nurtured. To touch the light, to feel nature, to connect to people... the accumulation of these things gives shape to the heart. It's the same even for Nobodies who do not have hearts.
From this tidbit I gather that several factors come into play when it goes for a new "heart-bud" to blossom and develop.
Furthermore, like JustSnilloc pointed out, that new hearts can be born in existences not meant to have hearts has been subtly hinted several times already and the "a heart can develop and being formed"-part was even spilled out word for word by Nomura using Ventus' injured heart as an example.
Nomura in the BBS Ultimania said:
-- Ventus awakens with Sora's help, but at first his eyes are blank, and when he first meets Terra and Aqua he falls asleep under their barrage of questions.
Nomura: At that time, although Ventus has awakened, his heart is not fully formed. The imagery is the same as the first week after Roxas entered the organisation in "KH Days", when he was spacing out.
This lines up
exactly with the stuff that Ansem the Wise explains to Riku. Ven's heart was nearly destroyed due to Xehanort's abuse and Sora's newborn heart helped it so it won't fully disappear, that was "touching the light" as Ansem put it, yet Ven's heart only started to fully heal and "reform" when he got to "feel nature" at the Land of Departure and "connected with people", in his case Aqua, Terra and Eraqus who took care of Ven and helped heal his heart.
Vanitas's newborn heart got most likely formed and shaped by MX, which would also explain the golden eyes if Xehanort decided to place a fragment inside Vanitas' heart already back then.
I could search for many more but here are some more hints from Nomura from various sources:
Nomura in Director's Secret Report said:
Until now in the Kingdom Hearts (hereafter KH) Series, there have been 2 types of "Kingdom Hearts" referring to the Heart of Worlds and the Heart of Men, could you explain the mechanics of this?
Think of the basic setting of KH as "All life has a heart". The heart of a world can be considered the things of nature; for example, the trees in a forest, a sea or river, a flower and so forth. When they all come together to form a world a large heart will come into existence. And concerning the hearts designated to men, all the hearts of humans and animals living in the world are integrated. As for Kingdom Hearts, think of it as if the heart is essentially the culmination of an invisible "Proof of Life"
Nomura in 358/2 days Famitsu said:
–What is the definition of a heart in Kingdom Hearts?
Nomura: It is the theme of the series. To explain it simply, a person has a body, a soul, and a heart. As an image, the soul is the life source, without it a person would be dead. Since the heart doesn’t have a form, memories play an important part in forming a heart. Also, the heart isn’t limited to people, but to all things. I tried to explain this concept to Disney, and they merely said that it must be an Eastern way of thinking. It may be interesting how overseas players think of it.
Coded Famitsu said:
Data Sora had a heart, didn’t he?
Nomura: Theoretically he doesn’t, but I entrust the answer to the imaginations of those who’ve seen the ending.
Coded Ultimania said:
Data Sora can newly obtain a legitimate Keyblade during his adventure, but are there changes to the real Keyblade when that happens?
Nomura: No, it’s a data version the entire time. However like with the first Keyblade, it wasn’t created by someone else. It comes from the heart’s connections with the data, hinting towards the story theme, “Can a heart be born in an existence made of data?â€
In-game Coded Hollow Bastion said:
Pete: Peh, he's nothing but data. He doesn't even have a heart!
Goofy: That's not true! Sora has a heart. It even reached us.
Pete: ...What?
Donald: We've been watching, the whole time. No matter how tough things got, no matter how much danger he was in, Sora kept on fighting to help everybody.
Goofy: He even said he'd fight with us! His feelings, they're so deep, and so happy! That's how... that's how we know for sure! Sora has a heart, and it's inside of us!
Donald: Our connected hearts are our power!
Sora: Connected... hearts...
That one is a dead giveaway in relation to Dream Drop Distance. Even if he is not a Nobody, Data-Sora gained/gave birth to a heart due to connecting with Donald and Goofy (and most likely the real Sora too).
And more:
In-game Coded Hollow Bastion 2 said:
(A flash of light fills the screen. When it fades, the damage blocks are gone, and Sora has his keyblade back!)
Sora: ...What? What just happened? This is... my keyblade?
(Donald and Goofy get up and line up with Sora to face Pete)
Pete: What's going on here!? I thought Maleficent destroyed that thing...
Voice: It looks like a new power has emerged from inside you.
(The camera turns to the entrance, revealing the speaker)
Sora: Mickey!
(Mickey enters the room and stands with the party)
Sora: What's going on? What's this new power?
Mickey: I don't know all the details, but... I think something has awakened inside of you. The keyblade is tightly connected to the Power of the Heart.
Yet, an old friend told me that the Heart can't be turned into Data.
Still, as you came up all this way, we developed a Bond. It might have created something new, something that goes beyond data. I'm sure it's a unique new power that you obtained through the bonds with your friends across the worlds.
Obvious reference to Ansem the Wise, and what is Mickey actually meaning here with "created something new, something beyond data"?
Right, a heart as Dream Drop Distance shows us now.
Seeing and remembering all those subtle hints scattered (and I bet those I picked out from my own memory aren't even all there are) I would actually wonder why people would be so surprised about it now being confirmed in DDD.
I always felt that, for example, Naminé and Roxas were way too emotional and "human" to be without a heart and I won't be surprised if they both grew a heart on their own that might be very nearly complete due to them co-existing with (and being connected to) their original selves.
(In Roxas' case Ven's heart might also have had a hand in helping to form Roxas' heart if we go by the premise that Roxas was actually carrying it the whole time).
So I personally would surely say this stuff about hearts makes not only sense in the whole overall plot but is also much easier to comprehend than Young Xehanort's/Ansem SoD's time travelling stuff.