The key is to look at the expectations on the client and caches when a particular status code is used.
Here's some chunks of RFC2616 that are useful to look at:
10.4.1. 400 Bad Request
The request could not be understood by the server due to malformed syntax. The client SHOULD NOT repeat the request without modifications.
This indicates that the request itself is completely wrong - either syntactically or by the protocol. Your specific case is really an application protocol error so this may indeed be appropriate.
10.4.6. 405 Method Not Allowed
The method specified in the Request-Line is not allowed for the resource identified by the Request-URI. The response MUST include an Allow header containing a list of valid methods for the requested resource.
This is a transient status code. If the DELETE refers specifically to the contact resources itself (e.g., DELETE /contacts/D9DF5176-EEE4-4C70-8DA7-BA57B82027A8) then this is probably the most appropriate status code. However, if the DELETE is on a different resource or a resource with a query (e.g., DELETE /contacts?index=12), then I would not return a 405. Then again, I usually steer clear of using DELETE with anything resembling a query.
10.4.10. 409 Conflict
The request could not be completed due to a conflict with the current state of the resource. This code is only allowed in situations where it is expected that the user might be able to resolve the conflict and resubmit the request. The response body SHOULD include enough information for the user to recognize the source of the conflict. Ideally, the response entity would include enough information for the user or user agent to fix the problem; however, that might not be possible and is not required.
This seems like the most appropriate status at first look. I would probably prefer a 400 in your case. A 409 would clearly indicate that there is a conflict with the resource but there really isn't anything that the requestor can do that could change the outcome short of completely altering the resource (i.e., add a contact first). Most of the 409 responses were optimistic concurrency failures such as trying to modify a resource that was modified since it was retrieved. For example, look at the concurrency failures returned by AtomServer built over Apache Adbera.
So with all of that. I would probably use something like 400 Cannot Delete Last Contact as the response line. Remember that you are allowed to change the phrase associated with the status code. This is a really good time to do such a thing.
409get's my vote in this case, as it's a conflict the user can resolve. That the common example is something else does not matter to me, other examples like this one exist.400is right out indeed, but there is something to say for405if you use actualDELETErequests... If not, 409 I say, but if you do... I see your dilemma.