Looks like they don't delete any cookies. They set a bunch of new cookies in your browser to indicate you want to opt-out.

From the FAQ: http://www.networkadvertising.org/managing/faqs.asp

9. How does the NAI Opt-out Tool work? The NAI Opt-out Tool replaces a network advertiser's unique online preference marketing cookie on your browser with a general opt-out cookie. It does not delete individual cookies nor does it necessarily replace other cookies delivered by network advertisers, such as those that are used for aggregate ad reporting or mere ad serving purposes. Such cookies allow network advertisers to change the sequence of ad banners, as well as track the aggregate number of ads delivered (impressions).

...

13. Can my browser settings interfere with the use of the NAI "Opt-out" Tool? Yes. Your browser must be set to accept 3rd party cookies in order for the NAI "Opt-out" tool to work.

(Loads as an image "active/not active")

  http://www.adbrite.com/mb/nai_optout_check.php?nocache=0.1742626
  HTTP/1.1 302 Found
  Location: http://www.networkadvertising.org/verify/cookie_exists.gif

(Loads as an image "check/x")

  http://www.adbrite.com/mb/nai_optout.php?nocache=5.057925E-02
  HTTP/1.1 302 Found
  Location: http://www.adbrite.com/mb/nai_optout.php?set=yes
  Set-Cookie: ut=deleted; expires=Sun, 18-Oct-2009 15:23:23 GMT; path=/; domain=.adbrite.com b=deleted; expires=Sun, 18-Oct-2009 15:23:23 GMT; path=/; domain=.adbrite.com untarget=1; expires=Thu, 15-Oct-2020 15:23:24 GMT; path=/; domain=adbrite.com

If they deleted the cookie then they would not be able to tell that you opted out they need to set a new cookie so that the next time they see you on their network they can specifically know that you are someone who doesn't want to be a part of their targeting.