There are a couple of recent threads on this topic that might help -
here and
hereI have one neutered and two entire boys. I find that if you rinse the area with cold water almost immediately it stops the smell from developing in all but the warmest weather, then you can add cleaning products. In your case though you might need to pressure wash to remove the accumulated urine and odour from between the paving slabs first...
I highly recommend Yard Clean as have mentioned in the above threads but there are many, cheaper, suggestions in there too :)