A relay device with efficient service change handling, and method there for, is provided. The relay comprises: a processor; a memory; a communication interface; and a plurality of connection objects, each of the plurality of connection objects comprising a respective queue of messages, each of the messages for relay in association with respective devices via the communication interface, the processor enabled to maintain, in the memory, a cache of associations between respective identifiers of the connection objects and identifiers associated with respective messages respectively queued therein; receive an indication of a service change to a given device; determine, from the cache, a subset of the plurality of connection objects comprising given messages associated with the given device; and, communicate only with the subset to apply an action associated with the service change to the given messages, while ignoring the remaining connection objects.