The WHERE clause in your UPDATE statement should include the status as well:
UPDATE EmailMaster SET status = 'I' WHERE mailid = 12345' AND status = 'P'
If the update fails, your code will know that another service has checked out the record.
But, seriously, I'd have some app running that is a manager, returning records for the services to work on. The services wouldn't have direct access to the database. All this manager would do is grab records from the database, track which service checked out which record and then release the records when the service is done with them. This can also give you the ability to set a "timeout". If a service crashes or is shutdown for some reason, the record can be returned to the pool so another service instance can check it out.