Try Kuala Lumpur, Malaysia. Cheapest 5 star hotels I know of (or good 4 Star Hotels at around NT$1500 / night right in the middle of town, which is also close to the Taipei ECO office) and cheap shopping. Cheap but good food, too.
I went on a package with EVA airs earlier this year, 4D/3N at NT$17000 only (4 Star Hotel).
No hassle at the TECO, takes 3 working days for the visa though you can get express, too.