1. I'm not aware of Exadata features that will make this specific operation faster
2. You're basic strategy sounds good
After splitting the max partition so it's empty, I'd look into switching to interval partitioning to avoid this problem happening again.
To do this, drop the max partition and set the interval:
alter table t drop partition pmax;
alter table t partition by interval ( ... );