Skill Link Icicle Spear doesn't kill Shedinja. It still has 1 out of 1 HP after each hit, so Sturdy activates on each hit. Rock Blast and Bolt Strike are not at all good coverage moves in BH; try things like Sacred Fire. Hell, Arm Thrust could work.
Thanks for the feedback; I guess whose sheddy wasn't running it killed was running sash and some other ability for some weird reason.