Chris Webb did a good article on this for something similar a while back which might help:

http://cwebbbi.wordpress.com/2011/12/22/replacing-cell-security-with-dimension-security/[/url]

I'm not sure that a dimension mapping every single user to services will be practical, nor creating all four of your roles for each service but you might have to. It's probably going to be better than creating subcubes for each service.