N.M. Stat. § 13-4-23
The manner of procuring and serving process in any action brought pursuant to the provisions of this act [13-4-21 to 13-4-24 NMSA 1978] when there has been, either, no designation of an agent in any such public contract, or where the agent named in such contract has died or removed from the state so that service cannot be had upon such agent, shall be as follows, to-wit: - the plaintiff, at the time of filing his complaint shall allege and set forth in his complaint or in an affidavit, to the satisfaction of the judge of the court having jurisdiction, that the defendant is one of the persons, partnerships or corporations contemplated in Section 1 [13-4-21 NMSA 1978] of this act, with the residence of said defendant, if known, and the further fact that said defendant has no designated agent within the state. Upon such showing being made, the judge shall make an order directing that service of process be made upon the defendant by delivering two copies of the process and of the complaint and of said order to the secretary of the state of New Mexico, with instructions and directions to the secretary of the state to forward one copy of said summons, complaint or other process, together with a copy of such order of the court to said defendant by registered mail to the address shown in the complaint or affidavit, as the case may be; and that in addition to making service upon the secretary of the state, the order of the court shall also direct that a copy of the process, together with a copy of the complaint and of said order accompanied by a notice that the same has been served upon the secretary of the state, pursuant to this act, be delivered to the defendant without the state. Proof of such service shall be made by affidavit filed in said action, and service shall be deemed complete thirty days from the date such personal service is made on the defendant.
NMS § 13-4-23