In general you should have no issues with either cloud-created or migrated shared mailboxes. Can you provide more info on any error messages you are seeing, such as the NDR when sending mail or the Autodiscover query results? Where are you MX and autodiscover records pointing at? If they point on-premises, you will need to have a recipient object representing the shared mailbox there, be it a mail user or contact or whatever. Or you can just create the shared mailbox using the default @tenant.onmicrosoft.com domain.

it says the mailbox cannot be found
autodiscover is pointing internal
mx records are at our mail filtering company

So you most likely need to have an object representing the newly created mailbox on the mail filtering company side, right? How are you provisioning those? Did you try with the @tenant.onmicrosoft.com address?

but we need it to accept mail on @company.com

if your MX record is pointing to your 3rd party hosted company, where is the 3rd party pointing, are they pointing to your on-prem exchange or O365?

they are pointing at hosted

By hosted, I'm guessing you mean that your inbound mail 3rd party company is pointing to O365. If that is the case then the shared mailbox should receive mail just fine from external domains, but if your 3rd party inbound company is pointing to your on-prem exchange then you may need an AD object mentioned by @Vasil Michev (MVP) for the shared mailbox so that your on-prem exchange will know where to send the mail.

no sorry 3rd party is pointing at our firewall and internal exchange

Wherever it's pointing, the idea is that you need to have a valid recipient object for it, otherwise mail will probably be rejected. This should easily be verified by checking the actual NDR message received, if any, or doing a message trace.

oh ok, then you will want to create an mailuser object or contact for that shared mailbox so exchange will know where to send it.
Follow Vasil Michev initial advice and that should correct your issue.

so i just need to point now at 365 since all mailboxes migrated?

yes you can point your 3rd party to O365 and that will also correct this issue. that way your on-prem exchange will not get involved. you can also just point your MX record to o365 and not use the 3rd party company. either way.

and if i dont i need to create it on prem first?
are there any gotchas i need to know about before changing