Citation needed for your assertion that VWAP is "REALLY easy to achieve".
Trading randomly during any given time period probably comes close to achieving VWAP. I'm sure something a little more intelligent could probably achieve it in expectation.
I can say with a great deal of confidence that a "random" VWAP algorithm would, on average, suck.
Many brokers will guarantee an execution at VWAP. It's a competitive business. The last time I put in such an order, I traded a double-digit percentage of the day's volume and paid 10bp commission (0.10%).
Plus, if you are dealing with a large broker they may just cross your order with an offsetting order (or their own position, execute nothing in the market and keep the entire premium.