If I was a company faced with that problem I look to see if I could take the money off shore and pay through wire transfers if the fees were cheaper than the negative interest rate being charge.
If the rates go negative enough banks will set up cash management tools where money is held as cash rather than on deposit at the bank (i.e. banks won't be able to lend against it).
The existing interbank system couldn't be used for that though, so a parallel reconciliation, netting, and transfer system would have to be set up and dealing with physical cash is fairly expensive (don't forget insurance). I wouldn't expect it unless rates go below -1% and maybe even further.
