You could try the Lock method which let's you put a new screen lock, but also add a message on the screen and an alternate number to call you if someone finds it. This doesn't need Location on, and if the phone is off it will activate when turned on and has data.
ADM can also ring it loudly for 5 minutes when on, I assume you dialled it as well.