Thats very strange...why wouldnt the police run a VIN to tell you if its stolen? You aren't asking for the identity of the owner, just a "yes" or "no".
If they don't make the information available, how can they hold buyers responsible for buying stolen goods? That makes no sense. If what they say is true, the only way you can find out if its stolen is to buy it and take it to the DMV to transfer the title only to have your new vehicle impounded. You would think they would design their system to catch the thieves, not punish lawbiding citizens.