I understand your pain dean, I happen to work for a rather security paranoid (and rightfully so) organization with pages and pages of rules regarding computer use and installed programs. All installed programs have to be OKed from my boss, her boss.. then Wash DC. First thing I did, before I even hinted at installing anything, was to talk with my bosses boss, and with my boss and explain what programs I would like to install and their purpose. I also explained my desire to gain the CEH and to work on security learning in general as a future focus of my career.
After going through all the hoops, I have basically been given free reign to do as I like within proper bounds. If I am going to do any scans I of course have to let the proper levels of boss-hood know, and get consent etc. You just have to remember to cover your own 4ss first and foremost. If you happen to scan something, and find a vulnerability.. you don't say a thing until you have gotten written or emailed permission to scan. Heck, I had to get rid of Putty the other day, because a new policy regarding that specific program was implemented after a compromised machine was found using port 22 to connect out. Not all policies make perfect sense, but remember your first priority is keeping a paycheck comming.
It's a sad thing hearing you got canned over it, but I think it is a good reminder to the rest of us to watch out for our organization's policies as well.
"Bad.. Good? I'm the guy with the gun"