You probably had OE set to share the Outlook contacts.  Removing Outlook
(part of Office) broke that so that OE no longer has an address book.
And a broken address book will generate the error message that you have.

To share Contacts between Outlook and Outlook Express
http://www.slipstick.com/contacts/oeshare.htm

Assuming that you had contacts that you still want, you'll need to
export the contacts from Outlook (not OE) to a CSV (comma Separated
Values) text file.

Then undo the contacts sharing (see the above article).

You can then import the CSV file into the OE WAB file.

And you can then uninstall Outlook (Office)

Also see:
The Windows Address Book (WAB)
http://www.insideoe.com/files/wab.htm

Do you have this Registry key?...

HKEY_CURRENT_USER\Software\Microsoft\WAB\WAB4

If not, STOP; If so, is there a DWORD named UseOutlook (NB: no space) and is
its value set to 1 (one)?

If not, STOP; If so, Address Book is configured to share contacts with
Outlook, even if you don't use it (can happen with the install of Office).
Change the value to 0 (zero) and all should be well.  (If that DWORD is not
present, don't create it, and don't alter any other DWORD values.)

Note that any changes (additions, deletions, edits) made while sharing was
enabled will not be available (displayed) in Address Book when sharing is
disabled.

NB: Expect the above to happen after installing any Outlook Update.  Also
expect the installs to "hijack" your default Mail Client to Outlook.