How does one block their personal information from appearing on
web-based search engines (zabasearch, akiba, etc) that list name(s),
phone number, address and even offer a background check for a fee?

As far as I know, you really can't stop them completely.

Because that information is considered public (i.e. you can find it in
any phonebook or courthouse) you really can't hide it.

If you had an unlisted phone number, you wouldn't appear in quite so
many pages.  But, now that they already have you in their databases,
that won't help.

You could also contact the sites individually and ask them to remove
your personal information.  Most will if they actually get your email.

Finally, your best bet it to call your local courthouse and ask them
if there is anything you can do to keep your personal information
private.