Can email box exist on the on-premise mail servers and the Office 365 cloud?

Technically it can, depending on the migration method. But it's not supported.

So if the outlook is trying to connect to Office 365  server, it should not exist on the local on-premise server? They have reported it as problem trying to connect to Office 365 but they all have an account on the on-premise server

Yes. Newer versions of Outlook have priority check for mailboxes in O365, but that only applies to configuring the mailbox. Other functionalities that depend on autodiscover will also be impacted in such configuration, as I mentioned above having mailboxes both on-premises and in O365 is not supported.

Mailbox would be there at one place only.its not recommended at all,if the mailbox is existing in both environment then user will face the issue in  accessing the mails.

If it's existing then you have to export the mails from o365 to pst. Delete the mailbox from cloud. Resync the Id from on Prem and move the mailbox online.

Before doing any step ,
Check the mailbox properties if it's showing as remote mailbox. If it is ,then the mailbox is in O365
You can run the below command to check
Get-mailbox -identity mailboxid | FL

Also connect with online powershell and try to check from there too with the same command line
 Let me know if it help