The Doctor only thought that the Daleks were totally wiped out twice (after the Time War and presumably after the 2009 Dalek invasion of Earth); Rose also thought so one other time (it's not clear if the Doctor agreed). All the other times, we're given significant hints that the Daleks will return.
A single Dalek was seen to have survived in Dalek. No information is given about how it survived the Time War, although it was mortally wounded (until touched by Rose), so 'survived' is only loosely appropriate.
The Daleks in The Parting of the Ways "[fell] through time - crippled but alive". I believe the idea is that although the Doctor believed that he trapped them all, he missed this ship, although it was significantly damaged.
The Daleks in Doomsday escaped the Time War using the only known Void Ship. A Void Ship is removed from time and space while travelling, so it was not affected by Rose's actions in The Parting of the Ways. In other words, although she thought she killed them all (like the Doctor thought he trapped them all), she missed some.
The Daleks in New York are indeed the same Daleks as we saw in Doomsday (Sec and the Cult). We knew that these Daleks survived, so were waiting for them to reappear. They didn't really manage to get very far before we see them again (in fact, they're really worse off than they were at the end of Doomsday).
The Daleks in Journey's End come from Dalek Caan, and we know that he survived the events in New York with an "emergency temporal shift" again; i.e. in this case we were again expecting him to return (the Doctor even says this). He's much more successful in restoring the Daleks this time, of course.
The Daleks in Victory of the Daleks come from a single ship that survived the events of Journey's End (i.e. this is just like the single ship that survived the Time War). It's not known exactly how they managed to achieve this - it's the biggest stretch of all, IMO.
The Daleks are seen again in The Pandorica Opens, although only briefly. One of these was The Eternal (the yellow one), who we saw escape through the Time corridor in Victory of the Daleks; i.e. this is another case where we know that they weren't all wiped out.
As far as we know, these Daleks are still doing fine, and so it's reasonable to expect them to return in the Doctor's future.
The Doctor doesn't (except when he does) alter his own timeline. In his timeline, all the Time Lords (other than himself and the Master) were trapped, so that's what he has to accept. He can't go back and save individual Time Lords, because that isn't what happened (although it's possible that others were safe, like the Master, and he (and we) don't know about it yet).
As far as we know, the Doctor is not able to overcome the lock on the Time War. Although Dalek Caan did manage to do this, it drove him insane; even if the Doctor could match this, he wouldn't necessarily consider it an acceptable price. This is perhaps "cheating", but it's cheating with a significantly high cost.
Out-of-universe, the answer is clearly that the writers want a decisive and definitive end to the battle that they are writing, but then writers of future episodes decide that the Daleks are such a great enemy that they need to be brought back somehow.
The "Time War" is a critical part of the 8th and later Doctors' past. The writers needed this to involve the most significant enemy possible, and it needed to be a stalemate, to explain why the Doctor wasn't still fighting (or why we aren't all Dalek slaves). It seems reasonable that we were told that (and the Doctor believed that) the Daleks were all gone at the start of the 9th Doctor's episodes.
Fooling the Doctor once (I don't really count the one surviver in Dalek) isn't that unreasonable, and fooling Rose is perfectly acceptable (it's not like she had any experience manipulating the vortex). The second time, after Journey's End, does seem like a bit of a "cheat", although I don't recall the Doctor personally saying that he believed that every Dalek was dead.
A popular enemy is like a cockroach - you can never be rid of them.