The first way is broken - Visio tends to lose lines, gets line widths wrong etc.
To generate a good EPS, first select "File|Print" from Visio, and select "Wine Postscript Driver" from the list of printers. Check the "print to file" checkbox and press OK. Save your file as name.ps.
To convert the PS file to EPS, use the "ps2eps" program (google for it). The command line to generate the file is "ps2eps -f name.ps".
To automate the process, I have a makefile for my Latex files. The makefile looks like this (don't forget that the lines with commands must be prefixed with a tab):
PICS = pics/file1.eps pics/file2.eps
paper.dvi: paper.tex $(PICS)
latex paper
bibtex paper
latex paper
latex paper
%.eps : %.ps
ps2eps -f $<