Oh, sorry! I've forgotten to post the call. Following is the call and the instanziation of the map (With VertexList=vecS this will work):

   // Get the index map

       typedef property_map<BGLGraph, VertexID VertexContainer::*>::type IndexMap;

   IndexMap im = get(&VertexContainer::m_idVertex, graphIn);

   // Create a predecessor map over the indices.
       BGLVertexDescriptor startDescriptor;
       idMapperIn.mapIDs(this->getStartID(), startDescriptor);

       std::vector<BGLVertexDescriptor> p(num_vertices(graphIn));

       p[this->getStartID()] = startDescriptor;

       breadth_first_search(
                 graphIn
               , startDescriptor
               , vertex_index_map(im).visitor(make_bfs_visitor(record_predecessors(&p[0], boost::on_tree_edge())))
       );

idMapperIn is a local class to map IDs to a valid vertex descriptor.