try stopping nagios, opening up your status.dat (do an 'updatedb' then 'locate status.dat') and deleting any entries pertaining to that service, then starting up nagios again.
other than that, it must be somewhere in your configs. Do a 'grep ./*' in your config directory, then open up each file you find in vi (vi filename.cfg). you can search in vi by typing /whateverword and hitting enter.
did you make sure it isn't sitting in the host_name list for that service definition, along with a bunch of other hosts?