The impact of a temporary Optional instance is negligible. Usually the JVM will detect its temporary nature and optimize away the instance. Even if the temporary instance creation is not optimized away, the impact of one single temporary object on the memory management is ridiculously low. See also GC overhead of Optional<T> in Java.
However, if the map is mutable, you can use the following trick:
public static MyEnum fromString(String value) {
return enumMap.computeIfAbsent(value, v -> {
throw new IllegalArgumentException("Unsupported value: " + v); });
}
Note that the Map is not modified by this code but still must be mutable as an immutable map might throw an UnsupportedOperation exception for the attempt to use computeIfAbsent without ever checking whether the operation would really modify the map.
But in the end, there is nothing wrong with Optional. But note that the code in your question is wrong. The lambda expression you pass to the method Optional.orElseThrow is meant to supply the desired exception, not to throw it:
public static MyEnum fromString(String value) {
return Optional.ofNullable(enumMap.get(value)).orElseThrow(() ->
new IllegalArgumentException("Unsupported value: " + value) // just return it
);
}