Can't speak for the police, but ambulance staff, if asked to remove their shoes, explain that they are not permitted to do so. If the patient cannot be brought to the door, they apologise for not removing their footwear and enter the house. They also carry plastic covers for their footwear which they can put on as well.
The same rules apply in some other circumstances, for example if they need to enter a temple (Bhuddist, Hindu or that of any other religion) as well as a mosque.
I'd guess that similar procedures apply to the police, possibly except in cases where they enter the house to comfort the bereaved (for example if the officer was a family liason officer).