Julie, I agree with you completely.  I also tried to work with them.
While I gave them next day, and sometimes same day service, I had
to call for every single check I ever got.  You shouldn't have to call
and plead with the person cutting checks for payment for work done
months ago.  Like you said, If they go out of business, there may be
someone out there who cares about their searchers, and about paying
them in a timely manner.