Hello Tim and All,
Many times we can analyze a problem IF we have got enough information. I do
all the time over the phone with bee club members. I will try here.
Tim wrote:
  This time I  waited 5 days and released the queen. She was
> imediately balled.

1. If enough time has passed for the hive to be completely  absent  of
brood of any kind if you do not have laying workers yet  they are not far
off.

Laying workers could be the problem. If so introduce your newly arrived
queen (now in push in cage)   into a nuc with brood from another hive and
once established introduce the nuc into the hive
 OR
 simply forget requeening and combine with a newspaper with another hive
Or
 shake the bees out and take the equipment.

2. The hive could be queenright.
The queen which flew  off    could have  returned  and is in the hive
OR
the original queen is still in the hive and you missed her even with two
times  looking. Take all the frames out of the old hive, shake off the bees
and run the bees through a queen excluder. Presto you should come up with
the  queen IF indeed the hive is queenright.

 Simply re cage the queen in the push in cage during the process and    use
later in the old hive or elsewhere if necessary.


Sounds like  a huge amount of work but the process will go fast  and you
will learn in the process.
Sincerely,
Bob Harrison

"Hives which are  queenright   will not except a new queen with a few
exceptions (old queen with a pheromone  problem being one exception)"

"Advance stage laying workers  are hard if not impossible to requeen"

"Strong hives  right before the honey flow can be a challenge to requeen"