In a HATEOAS API links are returned which represent possible state transitions. A conforming client should just be retrieving and following those links, but if a non-conforming client is constructing URIs rather than following the supplied links what would be the most appropriate status code/response to return?

• 400 would work, together with some information in the response body - this is what we're currently doing
• 403 I guess would be wrong, as it implies that the request could never work - but potentially the link may be available in the future
• 404 sounds plausible - at this point in time the resource doesn't exist

What do people think? I know that conditional requests can handle requests based on stale responses (resulting in e.g. 412s), but this is a slightly different situation.