Hi,
How can I generate keys with certain restrictions?
Would something like that
<xsl:key name="usedTypes" match="@*[name() = 'type' and not(starts-with(name(),'xs:'))]" use="." />
work to select those attributes with the name type that do not start with xs: ?

Yes. In fact, the "name() = 'type'" part will already take
care of this.

Do I need to take care of namespaces? How?

It depends what your requirements are.
The name() function returns the actually used name, including the
namespace prefix. The same element may be represented with different
names in a document, depending on namespace prefixes are bound.
Thgere is a local-name() function for returning the name without any
namespace prefix. You also have the namespace-uri() function (or
something similar, check the spec).

If you want to match attributes named "type" but not in the
"http://www.foo.bar/mumble" namespace, the following match
 match="@*[local-name()='type' and
  not(namespace-uri()='http://www.foo.bar/mumble')]"
should do the trick, regardless of the attribute prefix. It should
match 'type' attributes from every other namespace including the
default namespace (untested).