Dr. Bellows knows there is something very peculiar about Tony and tries hard to figure out what it is but the clues are so disparate that he can never put it together. But there are two things he should have been able to figure out;
1) The decorative bottle was unnaturally ‘special’ to Tony.
2) Tony has known a women named Jeannie ever since he returned from the failed orbital mission when he landed on the beach.
(I guess Dr. Bellows just thought himself a little crazy when all unexplainable things happen and he was the only witness.)

Examples:
In the first episode (“The Lady in the Bottle”) Tony told Dr. Bellows about the beautiful blond genie on the beach who saved him. Then at the end of that episode Tony frantically retrieved the bottle from the garbage and in front of Dr. Bellows ordered genie/Jeannie to come out (she did not). In another episode (towards the end of the first season) Dr. Bellows overheard Tony talking to the bottle, saying “You know I’d to like to marry you but people wouldn’t understand.” In episode15 (“Too Many Tonys”) Dr. Bellows found Jeannie (a blond) cooking for Tony in his kitchen and got the idea they were engaged. In episode 50 (“One Of Our Bottles Is Missing”) Amanda wants to copy Tony’s decorative bottle, and Tony breaks into their house to get it back. (He breaks into their house again to get it back in episode 132 (“Jeannie and the Curious Kid”)). In episode 56 (“A Secretary Is Not A Toy”) Jeannie became General Peterson’s secretary and Dr. Bellows did remember she was the women in Tony’s kitchen (his finance) even though Tony denied it (although Dr. Bellow’s overheard them arguing in General Peterson’s office). In episode 69 (“Who Are You Calling A Genie?”) Jeannie joins a tour Tony is giving at NASA and gets knocked out by Dr. Bellows when he opened the door into her head - Dr. Bellows heard Tony trying to wake her up calling her Jeannie and again thought he recognized her. And then Tony at first was trying to keep her from receiving medical attention, then was exceptionally interested in her condition when she was taken to the hospital. The coup de grace was in episode 83 (“Divorce, Genie Style”) when Amanda Bellows found a women in a harem costume named Jeannie at Tony’s house and thought they were secretly married and tried to help arrange for a divorce because Tony was an emotionally abusive husband.

The thing about episodic sitcoms in those days is you weren't suppose to remember what happen last week or on previous seasons. That's why I think they used the same actors over and over playing different characters. Fortunatly todays sitcoms give the viewers more credit!

The other thing was that after awhile, Dr. Bellows stopped trying to get to the bottom of the mystery with Tony. This was around the fourth season, and I remember him giving Tony a speech where he basically said, "No, I'm not going to try to figure out what's going on here, because I know that I'll end up in analysis again." After this point, it was up to Mrs. Bellows to be the one who noticed all the wackiness that was going on, and the series started losing steam. It didn't help that General Peterson, an old-school military man who acted fatherly at times toward Tony, was replaced by Gen. Schaeffer, who acted more like Mr. Mooney from "The Lucy Show", always bellowing and threatening.

Jeannie could've at times (in moments we didn't see) put curses on The Bellowses to make them forget what they previously learned.

Poor Dr Bellows,he went through hell! But some stuff happened that was just so unexplainable and Dr Bellows just let it go.It would frustrate me but thats what tv is.

I really couldn't stand Dr. Bellows.

"Bellows. Lt. Colonel DOCTOR Bellows to you! God, I won't miss him. It amazes me how he and Sam (WAY more on her in a bit, Tony!) are the exact same rank...While she commands respect and loyalty, because she will give nothing less of herself, Bellows' style, if you can call it that, was always just belittling, aggravating, snoopy... but never mind, I don't want to think about him."

That's what Major Healey told me to type.