Couple of things come to mind. We implement that sort of thing regularly. First if you can let me know what brand and part number relay you are using. Also do you have any contact protection such as an MOV or other type? Also how are you driving the relay? Single or double coil. Also some relays are called latching but are actually impulse relays. They behave in a different manner.