"Umgekehrt wird ein Stiefel d'raus"
I'll propose somewhat the reverse of what Magnus envisoned. In detail:
Categorised pages contain no special markup. Contrariwise, the category pages contain special links (syntactically different from normal ones) to pages considered in that category.
* Why is this scheme better than we do now (plain old links from a category to categorised pages)?
Scripts can tell that e.g. {{Compilers}} is in category [[Computer science]] but [[Mathematics]] or [[1950s]] is not. It's possible to automatically show (e.g. on the article bottom) links to the categories a page is in, to restrict searches to pages in category X, etc.
* Why is this scheme better than Magnus's (noting on a page itself that it belongs to categories X, Y, Z)?
Almost no good category list is just a random jumble of links. For example [[Prime ministers of Great Britain]] should probably be sorted in chronological order. "Proper" categories like [[Computer science]] are best represented by dividing the listing into subfields (as done in the current page). Magnus's scheme could support this via more complicated syntax (e.g. {{{CATEGORY P.M. of Great Britain;1985}}}, or {{{CATEGORY Comuter science;Algorithms}}}), but that reeks a bit of overengineering. Plus writers would have to coordinate their efforts (choose the same subcategorisation, and/or sort order) -- coordination is easier done on a single page (the category) than across a number of pages.
So the promise of "just editing one page instead of two or more" is a fallacy IMO. Even with the extended synatx above, you'd first have to check out the category page(s) to see the existing layout before you could sensibly write the correct category link(s).
If one doesn't want to put too much work into categorisation, and really wants to only let the link show up on the category page in a random location, my scheme could support this as well. Imagine a "put this page into this categories" box separate from the normal text edit box. Putting one or more categories there will add special links back to this topic onto the end of these pages. They'd be put into a distinct section, e.g. named "unsorted links". People tending to the category page can take and move these to a more proper position. I'm not sure whether we /want/ to support this kind of laziness by the original authors, though.
Concerns were raised that links from a categorised page to a category are more easily processed automatically than the other way around. My response is that this is an implementation detail -- one can always keep a seperate "backlink" index seperate from the main page texts for optimisation.