Nun, über die 250er Grenze kommst Du natürlich supported nicht hinaus. Die Freigabe kannst Du natürlich auch z.B. über einen Workflow erstellen (Custom Activity http://crm40sharestep.codeplex.com/ ). Hiermit wirst Du dann jedoch immer noch in 250er Schritten die Auswahl treffen müssen, um entsprechende Freigaben zu sezten.
Aber in diesem Zusammenhang interessiert natürlich, warum Du überhaupt für 4000 User eine Freigabe setzen musst. Was ist das Ziel? Was soll mit der Freigabe erzielt werden?