Creo que la librería que estás usando (POI) es lo mejor para tus propósitos. A veces el problema puede estar en un código no optimizado.

De todos modos:
<h2>Excel como Base de Datos</h2>

En Java puedes leer hojas de Excel como si accedieras a una Base de Datos.

Para ello necesitas añadir los drivers [JDBC ODBC][1] a tu proyecto.

Te dejo un código de ejemplo, publicado en [Java2s][2].
Se supone en el ejemplo que tienes una hoja llamada `Sheet1` y en dicha hoja tienes columnas llamadas `FirstName`, `LastName`. Consultas como si fuese una base de datos, obtienes un `rs`y operas con los valores devueltos.     
    
    
    import java.sql.Connection;
    import java.sql.DriverManager;
    import java.sql.ResultSet;
    import java.sql.Statement;
    
    public class Main {
    
      public static Connection getConnection() throws Exception {
        String driver = "sun.jdbc.odbc.JdbcOdbcDriver";
        String url = "jdbc:odbc:excelDB";
        String username = "yourName";
        String password = "yourPass";
        Class.forName(driver);
        return DriverManager.getConnection(url, username, password);
      }
    
      public static void main(String args[]) throws Exception {
        Connection conn = null;
        Statement stmt = null;
        ResultSet rs = null;
    
        conn = getConnection();
        stmt = conn.createStatement();
        String excelQuery = "select * from [Sheet1$]";
        rs = stmt.executeQuery(excelQuery);
    
        while (rs.next()) {
          System.out.println(rs.getString("FirstName") + " " + rs.getString("LastName"));
        }
        
        rs.close();
        stmt.close();
        conn.close();
      }
    }

<hr>
<h2>Otra librería</h2>
Existe también esta librería llamada [JExcelApi][3], la puedes probar.


  [1]: http://www.java2s.com/Code/Jar/j/Downloadjdbcjar.htm
  [2]: http://www.java2s.com/Tutorial/Java/0340__Database/AJDBCProgramtoAccessReadMicrosoftExcel.htm
  [3]: http://jexcelapi.sourceforge.net