I get this a lot, but it is definately channel dependent. In the UK BBC stations come back very very quickly, but local regional stations come back very slowly (Century FM is very slow).

I also find this with RDS Clock sync's too.