High frequency quasi-normal modes for black holes with generic singularities: II. Asymptotically non-flat spacetimes