I just added a checkbox called Checkbox1 to my test program, and put
Checkbox1.Checked = Not (Checkbox1.Checked)
in a button_Click event and it worked just fine - everytime I clicked the button the checkbox changed state.
There must be something else going on in your code - I would suspect that the Map1.Get("autosearch") is not returning the value you think it is.
Do you get an error or does it just not work.
Oh, and not to forget
Dim CheckBox1 As CheckBox
in Globals.