The -Verbose output uses stream #4, if that's what you're after. The Remove-Computer cmdlet doesn't usually write anything to the normal Success stream (#1) so there's nothing for the Out-File to write. See help about_Redirection.
You could eliminate the Pipe and the Out-File and add "4>&1 >> RemovedComputers.Txt" after the "-Verbose" parameter.
Or, if you just want to know which computers were removed, and which computers were not removed (and why they weren't), you could try something like this:
Try {
Remove-ADComputer "<ComputerName>" -Confirm:$False -Verbose -ErrorAction STOP
"Removed '<ComputerName>'" | Out-File -FilePath "<FilePath>\RemovedComputers.txt" -Append
}
Catch{
"Failed to removed '<ComputerName>'" | Out-File -FilePath "<FilePath>\RemovedComputers.txt" -Append
$_ | Out-File -FilePath "<FilePath>\RemovedComputers.txt" -Append # writes the exception
}