i would replace all vacuum hoses with new metric ones

cheap at Hong Kong ebay (1 meter / 3ft minimum order per size) hehe ... all rubber hoses are recommended to be replaced every 6 years, especially the ones around the engine (i mean they get HOT really whenever you drive).
also, replacing VSV for EGR is a bitch, I ended up going to local shop and paying $90 labor for replacement (my own new part). what makes you think it's the VSV fault ?
do you have any vacuum leaks?
as per EGR valve, it might need cleaning, there is a DIY here on it in sticky section, but i have to warn you that Toyota used cheap quality bolts to exhaust pipe at the factory, so they might get broken, and if that happens ... well you will see.