Also, Fawkes did have some connection with Harry after he returned from Azkaban - he asked Harry to help him destroy the place, and it's clear he asked the same of Dumbledore (perhaps many times).

So he's not totally off the mark in thinking that Fawkes would come to him - in that case he'd be agreeing to do what Fawkes wants, instead of restraining him like Dumbledore usually does. I bet if Harry called to Fawkes with a wish to go to Azkaban and destroy it, Fawkes would be there to take him in a heartbeat.