Startups: Companies that are in their initial stages of business and typically developing a business model and seeking financing.
Your incorporation and tax filings prove the company exists, but that isn't what verification is checking. The published criteria are about what the company is and does:
"Develop a software-based product or service that is owned by your company. Be privately held and for-profit. Be headquartered in a country where Azure services are available. Not have received more than $350,000 in lifetime free Azure credits. Not have raised Series C funding or later. Not be an educational institution, government organization, consultancy, or agency. Not be involved in cryptocurrency mining."
Two of those are worth looking at honestly. The product has to be owned by your company rather than built for clients, and consultancies and agencies are excluded outright. A lot of registered software companies are actually services businesses, so it's worth checking that before assuming the problem is documentation.
On appealing or resubmitting, there's no published guidance. The documentation doesn't describe what happens after a failed verification.
Help make this community better for everyone: if this answer resolved your issue, please accept it or leave an upvote. If not, share more details in a comment so we can continue the discussion and find the right solution.