Automation feedback - when to think about parallelization

I've designed a few automated testing systems now. A frequent anti-patten I've seen is using UI automation tools such as selenium to drive acceptance tests. One of the big pains is that as a project grows this system becomes more and more cumbersome, requires a lot of maitenance (to the point the cost of keeping them is questionable) and slows down feedback. The main goals to aim for are:

1.  Feasible to implement in terms of development skills
2.  Low cost in terms of time and maitenenace effort
3.  Effective and timely feedback

There are a couple of options I've come across

• Run a nightly build of UI tests (feedback once every 24 hours.)
• I tried this on a project for Google. It can work with small teams with limited checkins (~10 per day) where functionality is well defined and it is easy to blame revision numbers
• Parallelization - Ideally, each test runs concurrently on its own environment. 
• Problems I've faced:
• Can be dependant on Hardware if VMs aren't an option
• Usually BS trying to get corporate IT departments to give you what you need
• May miss bugs that would occur naturally when 2 users are concurrently using system that would be caught by running them on the same environment
• Continuous run
• The test suite just constantly builds and run tests
• Requires an extremely robust test suite or very basic site
• Can make debugging difficult because tracking the run against the build is very rapid
• Test prioritization
• Label tests as core and have them run very frequently (every checkin)
• Run tests labelled regression in a seperate pipeline
• This is usually very feasible

What do I recommend? Don't run acceptance tests at all through the UI. Use a proper domain model so it runs as a headless check and have general smoke tests. However, js heavy websites where business logic is happening a in the user interface means this isnt always feasible. I'd probably choose parallelization since it strikes well in terms of feasibility, cost and feedback.