Your colleague is right. From the spec (http://www.w3.org/Protocols/rfc2616/rfc2616-sec10.html#sec10.4.5), it says 404 is when "The server has not found anything matching the Request-URI". In your case, the server has found something, which it needs to return. You'll need to define the syntax of the entity returned in responses to this API, and return HTTP 200. It can be as simple as a boolean value, or anything that makes sense as long as its documented.
If the given "orderId" does not exist, it should return HTTP 404.