It sounds to me like it's not actually keying. For auto keyframe to work, you need to have a manual keyframe placed on the channel you want to keyframe. So set a manual key on visibility, then whenever you change the visibility, it should change automatically.
Also remember that visibility is a binary value (0 -> 1) while the graph editor works on floating point values (-n -> n). Make sure that it's interpolating the values correctly.
Imagination is more important than knowledge.