Strange interaction with the Immune keyword

I was playing paladin with Reckoning in play. My opponent plays Tundra Rhino and gives it Immune with Bestial Wrath. He attacks with it and it dies from Reckoning even though it had Immune.

Normally, things with immune can't be targeted, and if you play an AoE they just ignore the damage. But I guess since Reckoning hits a single target, but you aren't the one picking the target, it works differently.

Also, could you destroy an Immune minion with a random effect like Deadly Shot? Or would that work differently?

Immune minions are not immune to death, only damage and targetting.

Deadly Shot and Twisting Nether will still destroy immune minions.

Quote From KANSAS

I was playing paladin with Reckoning in play. My opponent plays Tundra Rhino and gives it Immune with Bestial Wrath. He attacks with it and it dies from Reckoning even though it had Immune.

Normally, things with immune can't be targeted, and if you play an AoE they just ignore the damage. But I guess since Reckoning hits a single target, but you aren't the one picking the target, it works differently.

Also, could you destroy an Immune minion with a random effect like Deadly Shot? Or would that work differently?

What you're describing sounds like correct interactions.  It can't take damage, but it can be destroyed.  Also it can't be targeted, but Reckoning isn't targeting the Rhino in this case.  At least not directly.  The Rhino is "targeted" only because it was the minion that triggered the trap