I know that the old 'Z' cars, hire cars with red z-plates, were not allowed across and most references still seem to say that that is the case from north to south. Have you googled it? This company
http://www.cyprus-car.com/ apparently allows its cars across (read the Car Rental Terms link). My (limited) experience is that these things can vary on a whim but if necessary you can park south side, walk across and hire in the north.
Lots of posts here
http://www.cyprus44.com/forums/301.asp suggest thats its easy from south to north.