I disagree that a private company need not seal its records - put simply since they do. I do not just give an answer to give it, but will add authority or links to other sources. Many attorneys offer services to send out letters attaching the court order to data brokers, for example this one in California. Most states offer some form of expungment and/or record sealing. See a list here. One national law firm boasts "Update over 650 background check companies with your newly cleared record".
Keep in mind to expunge a record does not mean to seal a record in all states. For example in California Penal Code Section 1203.4 will discard a conviction for a not-guilty plea and dismiss the case, but not seal the file. The conviction must be disclosed on applications for state or government employment. However, California Penal Code Section 851.8 does allow for record sealing and destruction of records along with the right to deny the arrest ever took place.
I have drafted and prepared for counsel dozens of record sealing orders in Nevada, California, and Texas. When someone obtains such an order sealing a record - an expectation of privacy is created. Specifically, when a record is sealed a right to privacy attaches. See, Gonzalez v. Spencer, 336 F.3d 832 (9th Cir.), cert. denied 157 L.Ed.2d 253, 124 S.Ct. 334 (2003) (attorney and law firm liable for accessing sealed case file without court authorization) See also, Keith H. v. Long Beach Unified Sch. Dist., 228 F.R.D. 652, 657 (C.D. Cal. 2005). (federal courts generally recognize that individuals - both parties and third parties - have a right of privacy, which protects against unwarranted disclosure of confidential and personal information.)
Once an order sealing a file, conviction, etc. is issued, the next step is sending certified letters to data brokers who feed the hundreds of smaller databases. The theme of the letter is that you have a right, in most cases, to deny the existence of a case and it is trampling on that right, thus must seal the record. I have yet to see a data broker not seal its record. Class action lawsuits such as Giddiens vs. LexisNexis, Henderson v. HireRight Solutions Inc.; Roe v. Intellicorp Records Inc.; and Robinson v. General Information Services Inc., have pushed background checking organizations into cooperating with a free service through the Foundation for Continuing Justice. However, not every company is on board and it’s possible for a person’s expungement to slip through the cracks.