Well, first of all, Voldemort is very confident in his protection. He left Kreacher alone on that island to die, with no way out, as far as he was concerned, and nobody to help him. He never would have imagined Kreacher could have got out of there.
'And then the Dark Lord sailed away, leaving Kreacher on the island ...'
Harry could see it happening. He watched Voldemort's white, snake-like face vanishing into darkness, those red eyes fixed pitilessly on the thrashing elf whose death would occur within minutes, whenever he succumbed to the desperate thirst that the burning potion caused its victim ... but here, Harry's imagination could go no further, for he could not see how Kreacher had escaped.
'How did you get away?' Harry asked, and he was not surprised to hear himself whispering.
'Master Regulus told Kreacher to come back,' he said.
'I know - but how did you escape the Inferi?'
Kreacher did not seem to understand.
'Master Regulus told Kreacher to come back,' he repeated.
'I know, but -'
'Well, it's obvious, isn't it, Harry?' said Ron. 'He Disapparated!'
'But ... you couldn't Apparate in and out of that cave,' said Harry, 'otherwise Dumbledore -'
'Elf magic isn't like wizard's magic, is it?' said Ron. 'I mean, they can Apparate and Disapparate in and out of Hogwarts when we can't.'
'Of course, Voldemort would have considered the ways of house-elves far beneath his notice, just like all the pure-bloods who treat them like animals ... it would never have occurred to him that they might have magic that he didn't.'
Harry Potter and the Deathly Hallows - pp.160-1 - Bloomsbury - chapter 10, Kreacher's Tale
And therefore he could never have joined the dots and worked out that it was Regulus who had stolen the locket. And Regulus wanted him to know.
I know I will be dead long before you read this
but I want you to know that it was I who discovered your secret.
Harry Potter and the Half-Blood Prince - p.569 - Bloomsbury - chapter 29, Flight of the Prince
We know that Voldemort never realised what Regulus had done. Never.
And how could the boy, or anybody else, know about the cave or penetrate its protection? The idea of the locket being stolen was absurd ...
Harry Potter and the Deathly Hallows - p.444 - Bloomsbury - chapter 27, The Final Hiding Place
He must have assumed that Regulus just fled. I know others speculated that Voldemort killed him, so presumably, after his disappearance, Voldemort didn't parade the fact that someone had left his service and he hadn't tracked them down.
It might seem to us that it was an oversight on his part, not to work out what Regulus had done. But he was very very confident in his protection and very, very disdainful towards Kreacher. It's thoroughly within character.
The only strange part, of course, is that Regulus wrote the not and so left a trail that could lead Voldemort to Grimmauld Place, Kreacher, and the locket. I suppose he trusted in Kreacher's ability to destroy the locket and perhaps also was confident that Voldemort wouldn't find his note until much, much later. He also forbade Kreacher from talking about it to Regulus's parents, keeping them fairly safe. Presumably Kreacher would've hidden from Voldemort, had he come calling and I doubt Mr and Mrs Black would've thought it worth mentioning Kreacher to Voldemort. Assuming he even remembered anything about the elf he left to die.