Note that if you use iCloud on a Mac and your iPad (or other iOS devices) (the same account), open tabs will appear on the iPad and vice versa in the iCloud Tabs section (next to bookmarks on iPad). This could be where such a suggestion is coming from. I would suggest clearing history and cookies/data on all devices using iCloud (yes you will lose logged in state for many sites and will need to re-sign in).
On your iOS devices, make sure you are clearing your history and data using the Settings app, and not by manually deleting entries in Safari's bookmark menu. You can also disable Safari with iCloud using the Settings app under the iCloud section.
After you have reset everything, when you want to visit sites and not keep history, you can use Safari's privacy mode. To do this in Safari (iOS 7), when you tap the address bar, tap Private above the keyboard on the left side to toggle privacy mode. If you are using a physical keyboard, this option will still show at the bottom of the screen.
I use Chrome as my main browser on iOS. There you tap the button on the top right (next to the address bar most of the time) and then tap New Incognito* Tab to enter incognito mode.