Unique Constraint in a RESTFul architecture

I see no reason to not return the appropriate HTTP code: 409 Conflict. This can be returned upon getting errors from your database.

It is nice for usability reasons to check if the e-mail address is unique before sending the request as you can prompt the user (and disable submit) to correct the problem. In any case server side verification is still advised.

This has nothing to do with protocol statelessness. Statelessness only says that the server shouldn't be the one saving session-related state (http://en.wikipedia.org/wiki/Stateless_protocol).

In your case, User resources are not session state - they are persistent resources stored on and exposed by the server. There is no reason wrt statelessness to force the client to do this check (by iteratively fetching and checking all User resources), and it makes more sense to have the server do it. Whether this check is done by the server as a part of POSTing a new User resource, or there exists a separate resource that enables this check -- it essentially makes no difference since the server is doing this check either way. If you use a separate resource to first check if it is OK to POST a new User, and then make a new request to actually do the POST -- then there is the possibility of duplicate e-mail addresses. In such cases, the expected behavior is that the server notifies the client that the POST request has failed (using an appropriate HTTP response code, just as it would for the first request by which the client checked that the e-mail is OK).

In short: the server does the "check", and the client should be able to handle situations in which the server notifies it that the check failed.