I clean with pbw, but only if the brewing equipment/buckets are really dirty. Otherwise I just sanitize with Iodophor--soaking everything for 1/2 hr or so and letting it air dry. I did recently go all-grain so, I have new everything (except bottles and bottling wand). For the bottles I usually put them in the dishwasher with some Iodophor and let them air dry. I don't soak them in Iodophor. Should I be soaking the bottles? I'm thinking of just buying new bottles and seeing if that's the problem.
PBW is great for the dirty work. I use (cheap) washing soda (aka laundry booster) for most of my beer cleaning duties, and (homemade) PBW when and where it counts, like cleaning hop bags (they get boiled in PBW), plate chiller, etc.
As long as your Iodophor is still active, it will sanitize fine. But it loses its activity after a day or so. You need to keep an eye on that. How about using Starsan instead? I makes me shiver to even imagine what brewing would be like without it.
Needless to say, before you can clean and sanitize bottles, there should be no layer of gunk inside them, that needs to be cleaned out first, with a good soak and rinse even a brush.
Realize your bottles need to be spotlessly clean on the inside. You can't sanitize anything that isn't clean in the first place.
Your dishwasher can't get water up those narrow necks. Anyone who claims that it does, should start analyzing how a dishwasher works. Use a bottle brush and a dishwash tub with hot water and a cleanser (washing soda, PBW) and scrub the insides. You can then rinse with one of those jet bottle washers that attaches to your faucet and spray hot water when you push a bottle down on them. Then sanitize properly right before use. I'd soak them in sanitizer, yes. Starsan works as long as the surface is wet with it. Once dry its sanitizing properties are nil.
I'd start there.
No need to buy new bottles. Even new bottles have dust in them, still need to be cleaned and sanitized. Grain contains lactobacillus and dust from milling settles everywhere. Mill outside!
When you bottle, the caps should be sanitized too. Again, Starsan is your best friend.