I feel I should be able to answer this myself, but I can't get my head around it.

Can I use the Any Phase ability on Rusted Sword on KL Joff despite him being immune to triggered effects?

OK. I'll give you my pat answer for this question.

Let's say I have Dany's Handmaiden in play and you have an attachment (oh, let's say Devious Intentions) on Joffrey. The Handmaiden is killed. Can I use her effect to discard the Devious Intentions? Of course, because immunity only protects from effects that are applied directly to the immune card. Dany's Handmaiden is applied completely to the attachment, affecting it directly and discarding it. Joff is only affected indirectly by losing the benefit of the attachment. So a "discard an attachment" effect can be used to take an attachment off of Joffrey. All that is clear, right?

Well, Rusted Sword is the same thing in reverse. Joffrey is not chosen by the effect and the direct effect is applied directly to the attachment card - putting it into play. It is not applied directly to the character the attachment is being put on any more than the Handmaiden's affect is when taking an attachment off. Granted, Joffrey changes indirectly when the attachment "arrives" in play, but immunity doesn't stop this kind of indirect effect.

Yeah, the handmaiden example makes it totally clear. I knew that existing attachments are not protected by immunities pertaining to the characters they're attached to, that's standard stuff from the FAQs. Of course this should also include the act of attaching attachments to characters. Thanks for the answer ktom. Had my brain in a twist somehow yesterday.