You are messaging a new lead/contact that does not exist in the Outreach system directly from Outlook or Gmail, but they're not appearing in Outreach after email deliveries and communications.
Emailing from Outlook and Gmail
For the Outreach add-in (Outlook) or the Outreach Everywhere Chrome extension (Gmail) to create new leads and contacts in the Outreach system that you're emailing, there is a setting under the system's admin Org settings page that needs to be enabled. The setting is labeled: Automatically create a prospect when sending an email using the Outreach extension or add-in.
If the above setting is disabled, then the record must be created manually, via the bulk create workflow, or by your CRM. The system is respecting the above admin setting that is configured by your Organization. If it is set to not auto-create new prospects that you're emailing, then the Outreach system will not create that record you're emailing in Outreach as it has to respect that setting.