Suggest you have a chat with your security people to see what would be acceptable. I suspect that merely removing the software on its own wouldnt be enough to satisfy them, youre going to have to remove the hardware (in which case its irrelevant whether the camera software is still on there or not) or somehow otherwise disable it (tippex on the lens? maybe even just a piece of masking tape?). If you really need to physically remove the lens i'm guessing it should be possible with a relatively small amount of violence, and if youre lucky the rest of the phone will still work afterwards.
My company finally realised that prohibition is a losing battle (difficult to find any phone without a camera these days), and have instead made everyone aware of their responsibilities and made us sign a form to that effect. If you really wanted to steal secrets with a camera there's not a lot they can do to stop you (unless youre prepared to have security so tight they search you every time you enter the building), so all they can really do is make sure you know what you shouldnt do (also means they can sue your arse into oblivion if you do something you shouldnt). Same thing applies to nearly any modern electronics device, e.g. mp3 players, thumbdrives etc.
