Warning: Cannot modify header information

So I have an odd seeming bug. I have some menu links that I was using nolink for a temporary placeholder on. The links in the menu were rendering as actual links that would send users to a 404 page. I started noticing in my logs that after someone went to a 404 because of the nolink, there were a bunch of session warnings.

If you were logged in you only saw this one:

  	Warning: Cannot modify header information - headers already sent by (output started at /public_html/includes/common.inc:2575) in drupal_send_headers() (line 1225 of /public_html/includes/bootstrap.inc).

But anonymous users who clicked on the nolink kicked out two additional warnings:

  Warning: session_start() [function.session-start]: Cannot send session cookie - headers already sent by (output started at /public_html/includes/common.inc:2575) in drupal_session_start() (line 278 of /public_html/includes/session.inc).
Warning: session_start() [function.session-start]: Cannot send session cache limiter - headers already sent (output started at /public_html/includes/common.inc:2575) in drupal_session_start() (line 278 of /public_html/includes/session.inc).

The only reason I think this has to do with this module is that it only happens on links created by this module. I've tried creating other 404s and no warnings.