Are there algorithms to exactly minimize NFAs which are sometimes efficient?
SAT solvers have been pretty good at this. See [1] for more; the method produces a minimal automaton in almost all cases. Following some references, Tsyganov [2] combined the Kameda-Weiner with local search methods.

I don't know if there are readily available implementations out there, but at least [1] describes the reduction to SAT. One can then use any available SAT solver.



[1] Geldenhuys, Jaco, Brink Van Der Merwe, and Lynette Van Zijl. "Reducing nondeterministic finite automata with SAT solvers." Finite-State Methods and Natural Language Processing. Springer Berlin Heidelberg, 2010. 81-92.

[2] Tsyganov, Andrey V. "Local Search Heuristics for NFA State Minimization Problem." International Journal of Communications, Network and System Sciences 5 (2012).