I had this problem a while ago. I'd paid Amazon to remove ads, and they were removed for a short time, until I used the wifi, and then they were back. I spent 45 minutes or more on the phone with second-tier customer service (the first tier bounced me fast to someone with more expertise.)
The solution finally was for Amazon to turn ads on again, then off again, and the no-ads finally took. But Amazon had to do that; it didn't work when I did it from the Manage Your Kindle page.