Iterative Budgeted Exponential Search (IBEX) is a general search algorithm that can limit the number of re-expansions performed in common problems like iterative-deepening tree search and search with inconsistent heuristics. IBEX has been adapted into a specific tree algorithm, Budgeted Tree Search (BTS), which behaves like IDA* when f-cost layers grow exponentially, but keeps the worst-case guarantees when this does not hold. The analogous algorithms on graphs, Budgeted Graph Search (BGS), does not have these same properties. This paper reformulates BGS into Efficient Budgeted Graph Search (BGS$_e$) showing how to implement the algorithm so that it behaves identically to A* when the heuristic is consistent, and retains the best-case performance otherwise. Experimental results validate the performance of BGS$_e$ on a range of theoretical and practical problem instances.