A strategy for exploring distributed state spaces using computational grids that run bag-of-task applications is discussed. The main idea is to use computational grid tools as a layer between the verification tool and the distributed shared resources, aggregating the vast background developed by researchers in grid computing. Hence, the computational grid deals with resource scalability, computational speedup, and reliability in a transparent manner for the verification tool. Experimental results using a state space generation tool for an object-oriented Petri nets and the OurGrid solution show that is possible to achieve speedup applying it to a private network environment. Moreover, when a wide distributed community is considered, the model size can be increased several times.