Will Nikon clean sensors for free under Warranty?

Should should get at least one cleaning out of Nikon Service.

Cleaning sensors can go very easily and well, and other times it can be a complete pain and take forever. But sooner or later you're going to have to rely on yourself to do it, or suffer the time and expensive of hiring it done. Hang in there and keep trying. Be careful, of course, but it's just one of those things you have to get used to doing, IMO. Obviously if you spend a lot of time shooting at small f-stops you're going to have to be even more thorough.

One tip: get used to doing it on a regular basis. (How often depends on how much you use the body--change lenses--and the environments you shoot in.) I've always found some of the spots harder to get off if they sit there forever. So whatever the schedule--once a week, two weeks, four weeks--just be consistent. And, once you get that oil off from the factory, it will be easier in future cleanings. The first few can be a PITA, but I've always found it gets better.