In embedded Lucene permissions are checked after lucene returned all results,That means if you want to search with page size 500,luene will search more that 500(default is 1000) doucuments and starts to check the permissions one by one. So the larger the page size you set ,the slower it will get. You should consider upgrading to Alfresco 4 and use Solr,in solr permissions are checked at query time ,it has better performance.
Have you ever configured "modified date" to use a different lucene analyzer.as I remember by default "created date" and "modified date" are configured to use same DateAnalyer in alfresco 3.4,so sorting by them should take nearly same time.