The Tcpmd5 guide for Bgpcep here
https://wiki.opendaylight.org/view/BGP_LS_PCEP:TCP_MD5_Guide#RESTCONF_Configuration
uses POST, but that can fail when data is already created, so I was trying to use PUT instead, which needs keys in URI.

I tried the following curl command. It is in bash, so data is in single quotes, and single quote inside is written as '"'"'.

curl -v -X PUT -H "Content-Type:application/xml" -d '<service xmlns="urn:opendaylight:params:xml:ns:yang:controller:config">
<type xmlns:x="urn:opendaylight:params:xml:ns:yang:controller:tcpmd5:cfg">x:key-access-factory</type>
<instance>
<name>global-key-access-factory</name>
<provider>/modules/module[type='"'"'native-key-access-factory'"'"'][name='"'"'global-key-access-factory'"'"']</provider>
</instance>
</service>' 127.0.0.1:8181/restconf/config/network-topology:network-topology/topology/topology-netconf/node/controller-config/yang-ext:mount/config:services/service/odl-tcpmd5-cfg:key-access-factory/config:instance/global-key-access-factory

Reply is code 400 with this text:
{"errors":{"error":[

{"error-type":"protocol","error-tag":"malformed-message","error-message":"Error parsing input: Unknown child(ren) node(s) detected, identified by: (urn:opendaylight:params:xml:ns:yang:controller:config)type, in: list instance"}

]}}

Is it a bug or am I doing something wrong?

The underlying exceptions are only visible on DEBUG level in karaf.log:
2015-05-12 16:22:06,062 | DEBUG | y-access-factory | RestCodec | 283 - org.opendaylight.controller.sal-rest-connector - 1.2.0.SNAPSHOT | Value is not instance of IdentityrefTypeDefinition but is class java.lang.String. Therefore NULL is used as translation of - odl-tcpmd5-cfg:key-access-factory
2015-05-12 16:22:06,066 | DEBUG | y-access-factory | XmlNormalizedNodeBodyReader | 283 - org.opendaylight.controller.sal-rest-connector - 1.2.0.SNAPSHOT | Error parsing xml input
java.lang.IllegalStateException: Unknown child(ren) node(s) detected, identified by: (urn:opendaylight:params:xml:ns:yang:controller:config)type, in: list instance
at com.google.common.base.Preconditions.checkState(Preconditions.java:197)[37:com.google.guava:18.0.0]
at org.opendaylight.yangtools.yang.data.impl.schema.SchemaUtils.findSchemaForChild(SchemaUtils.java:100)[74:org.opendaylight.yangtools.yang-data-impl:0.7.0.SNAPSHOT]

Note that the same log contains segment suggesting that ODL knows the Yang model I was referring to:
2015-05-12 16:20:27,775 | DEBUG | oupCloseable-6-1 | NetconfDeviceCommunicator | 197 - org.opendaylight.controller.sal-netconf-connector - 1.2.0.SNAPSHOT | RemoteDevice

{controller-config}: Message received <rpc-reply xmlns="urn:ietf:params:xml:ns:netconf:base:1.0" message-id="m-18">
<data xmlns="urn:ietf:params:xml:ns:yang:ietf-netconf-monitoring">// vi: set smarttab et sw=4 tabstop=4:
module odl-tcpmd5-cfg {
yang-version 1;
namespace "urn:opendaylight:params:xml:ns:yang:controller:tcpmd5:cfg";
prefix "tcpmd5";

import config { prefix config; revision-date 2013-04-05; }

organization "Cisco Systems, Inc.";

contact "Robert Varga <rovarga@cisco.com>";

description
"This module contains the base YANG definitions for
TCP MD5 Signature option.

Copyright (c)2014 Cisco Systems, Inc. All rights reserved.;

This program and the accompanying materials are made available
under the terms of the Eclipse Public License v1.0 which
accompanies this distribution, and is available at
http://www.eclipse.org/legal/epl-v10.html";

revision "2014-04-27" { description "Initial revision"; }

identity key-access-factory { description "Service representing a way for accessing key informtion."; base "config:service-type"; config:java-class "org.opendaylight.tcpmd5.api.KeyAccessFactory"; }

typedef rfc2385-key {
type string { length 1..80; }
}
}

</data>
</rpc-reply>

2015-05-12 16:20:27,775 | DEBUG | oupCloseable-6-1 | AbstractObjectCache | 41 - org.opendaylight.yangtools.object-cache-api - 0.7.0.SNAPSHOT | Looking up reference for QNameModule{ns=urn:ietf:params:xml:ns:yang:ietf-netconf-monitoring, rev=2010-10-04}
2015-05-12 16:20:27,775 | DEBUG | oupCloseable-6-1 | AbstractObjectCache | 41 - org.opendaylight.yangtools.object-cache-api - 0.7.0.SNAPSHOT | Looking up reference for (urn:ietf:params:xml:ns:yang:ietf-netconf-monitoring?revision=2010-10-04)data
2015-05-12 16:20:27,775 | DEBUG | oupCloseable-6-1 | nfRemoteSchemaYangSourceProvider | 197 - org.opendaylight.controller.sal-netconf-connector - 1.2.0.SNAPSHOT | RemoteDevice{controller-config}

: YANG Schema successfully retrieved for odl-tcpmd5-cfg:Optional.of(2014-04-27)
2015-05-12 16:20:27,776 | DEBUG | sing-executor-11 | AbstractObjectCache | 41 - org.opendaylight.yangtools.object-cache-api - 0.7.0.SNAPSHOT | Looking up reference for org.opendaylight.yangtools.yang.model.repo.spi.PotentialSchemaSource@3ca77319
2015-05-12 16:20:27,776 | DEBUG | sing-executor-11 | AbstractObjectCache | 41 - org.opendaylight.yangtools.object-cache-api - 0.7.0.SNAPSHOT | Looking up reference for org.opendaylight.yangtools.yang.model.repo.spi.PotentialSchemaSource@cf79e2c9
2015-05-12 16:20:27,776 | DEBUG | sing-executor-11 | TextToASTTransformer | 80 - org.opendaylight.yangtools.yang-parser-impl - 0.7.0.SNAPSHOT | Model NetconfYangTextSchemaSource{identifier=SourceIdentifier [name=odl-tcpmd5-cfg@2014-04-27], device=RemoteDevice{controller-config}} parsed successfully
2015-05-12 16:20:27,776 | DEBUG | sing-executor-11 | TextToASTTransformer | 80 - org.opendaylight.yangtools.yang-parser-impl - 0.7.0.SNAPSHOT | Model NetconfYangTextSchemaSource{identifier=SourceIdentifier [name=odl-tcpmd5-cfg@2014-04-27], device=RemoteDevice{controller-config}} validated successfully