Why does queued build only run after task cancelled/fails?

I have a PowerShell script running in an Azure DevOps pipeline. This script makes an API call to queue a build:

$Uri = 'https://dev.azure.com/{MY ORG}/{MY PROJECT}/_apis/build/builds?api-version=5.0'
Invoke-RestMethod -Uri $Uri -ContentType "application/json" -Headers headers -Method POST -Body ($buildBody | ConvertTo-Json)

There is a loop that makes a GET call to check the status of that build every few seconds. The task does not end until the build succeeds or an error is thrown.

while($buildOutput.status -ne "completed")
{
    Start-Sleep -s 60
    $buildOutput = Invoke-RestMethod -Uri $url -Headers headers
    $url = $buildOutput.url
    Write-Host "Current status of build: $buildOutput.status"
}

However, the build only kicks off now when the task running this script is cancelled or times out. I have reproduced this several times.

Has anybody had this problem before? Why does the queued build began as soon as I cancel this task? Is there some setting that I am missing?

Firstly, since you are queuing another build from current build please make sure you have enough parallel jobs on your organization, otherwise the target build status will show as notStarted as the build cannot get a free agent to run. It caused loop cannot be completed till current build timeout or cancelled.

Secondly, you are using queue build and get build rest api, the $Uri and $url is different, also, you loose $ before $headers in command $buildOutput = Invoke-RestMethod -Uri $url -Headers $headers.

I fixed the script(source build) as below and it works, please replace the build info to yours:

pool:
  vmImage: ubuntu-latest

steps:
- task: PowerShell@2
  inputs:
    targetType: 'inline'
    script: |
      $body = '
      { 
              "definition": {
                  "id": 603
              } 
      }
      '
      $personalToken = "$(personalToken)"
      $token =   [System.Convert]::ToBase64String([System.Text.Encoding]::ASCII.GetBytes(":$($personalToken)"))
      $header = @{authorization = "Basic $token"}
      $Uri = "https://dev.azure.com/{org}/{project}/_apis/build/builds?api-version=5.0"
      Write-Host $Uri
      $buildOutput = Invoke-RestMethod -Method Post -ContentType "application/json" -Uri $Uri -Body $body -Headers $header
      $buildid = $buildOutput.id
      $url = "https://dev.azure.com/{org}/{project}/_apis/build/builds/$buildid" +"?api-version=5.0"
      
      while($buildOutput.status -ne "completed")
      {
          Start-Sleep -s 10
          $buildOutput = Invoke-RestMethod -Uri $url -Headers $header
          $status = $buildOutput.status
          Write-Host "Current status of build: $status"
      }