There is no difference between the Outlook client for on-premises or Online.
Are you getting directed to the CRM 2013 client instead of CRM 2011?
Why do users get prompted to install the Outlook client after you do a rollup? Do they not already have the client, in which case they just need the rollup to be applied, not to reinstall the whole client (which will not have the latest rollup slipstreamed
in any case)
Hope this helps.
Adam Vero, Microsoft Certified Trainer | Microsoft Community Contributor 2011
UK CRM Guru Blog