It is in fact possible to get full Google Now functionality in a Google Apps domain. I've had it working for a long while.
Go to the Google Apps Admin Console (https://admin.google.com/AdminHome).
Navigate to Apps > Additional Google Services
You'll see a gray bar at the top of the screen ("Filter: Top featured services"). Click the "X" on the top right to disable that filter.
Scroll down to "Web History" and select "On for everyone."
Each user may then need to also enable Web History for his or her own account (https://www.google.com/settings/accounthistory/search).
No, it shouldn't be that hard, but, yes, that will work.