The most delicious vegan tacos come from the main Taqueria Sinaloa, located on 22nd and International in Fruitvale. That spot has 2 taco trucks in the parking lot. The truck that's more Easterly/farther away from International will reliably have incredible vegan tacos. You can get them by ordering veggie tacos without cheese or cream. They are $1.25 each.
There are two other Taqueria Sinaloa locations in Oakland, one by Lake Merritt and another on Fruitvale Ave & East 12th St, as well as a couple in Berkeley.