"chat not found" error when replying to user

We have a scenario where the user starts a conversation by calling our telegram bot. We extract the chat id from the message data when the user calls our bot

We use the chat id in order to reply the user by making a post call:
url - https://api.telegram.org/bot123321123321:token/sendPhoto
body - "chat_id":"123456789","parse_mode":"Markdown","text":"hi"}

The response is: error 400 "Bad Request: chat not found"

This only happens for some of the users while the rest are able to receive the messages. Is it possible that the chat id of this user was sent incorrectly by telegram on the first message? Or maybe this user has privacy settings? The same error is received when trying to make the same call from postman.

Thanks