Why I think this should be WONTFIXed? I still can't see any way how this would be implemented, considering problem that interwikis and categories can be included from templates.
You would just provide no interface to alter the categories that are added by templates, or generally speaking uncovered by template
??!! Why the subjunctive? Am I already blacklisted? Is no one reading my postings?
It already exists (HotCat-Gadget on commons)! The SoC proposal is moot. It has been done.[*] And for the day to day real-life applications (on commons for example) all the constructed pathological cases that were posted here are simply irrelevant.
[*] Oh, right, it has been done as a Javascript add-on, that may not count to some people. But please keep in mind that the category suggestion uses AJAX anyways, so there is no way (and no point for that matter) to built it into the interface (unless you also plan to abandon [[Category:..]] tags and change ta DB structure accordingly)