First you must mindread the bartender at the Phoenix Inn. He will reveal information about Halliwell and provide a hint about the key. If he does not mention the key or Halliwell you need to try again or you maybe bugged.
The key is located on the stairs near the pile of debris under the bridge; its equally spaced from the debris to the wall and is not part of the pile. If you are walking down Lanilor Lane from the Ministry you will find it on the left side stairs; its on the right side if you are coming from the teleporter shrine.
