The message isn't encrypted for each device; the message is encrypted once for the room, as part of a 'session' of messages - and then the key data for that session is shared with the devices who are allowed to read it. Thus you can share old session key data with other devices if you want, meaning that new devices /can/ see old messages, although we're still working through the UX for that. (Currently the only way to do it is by import/export session key data in settings and transferring it between devices).