Ok, I think we have it. Dogslow is reporting slow queries from the search API. See the dogslow report below.

I can replicate this locally using the following search, on a backup of our current data:
Whats the difference between the ADMINISTER and SYSTEM_ADMIN permission in JIRAs API

Resource Value
User CPU time 1991.668 msec
System CPU time 379.833 msec
Total CPU time 2371.501 msec
Elapsed time 20913.682 msec
Context switches 439 voluntary, 4187 involuntary

I haven't yet done exhaustive testing, but it seems like long search queries are much slower to return than short ones.

Title: Slow Request Watchdog: POST http://support.atlassian.com/api/search/
Undead request intercepted at: 04-01-2012 22:12:00 UTC

POST http://support.atlassian.com/api/search/
Thread ID: 47925307675104
Process ID: 16154
Parent PID: 16146
Started: 04-01-2012 22:11:35 UTC

File "/opt/python/domains/atlassian.com/answers/lib/python2.6/site-packages/django/db/models/query.py", line 300, in iterator
yield obj
File "/opt/python/domains/atlassian.com/answers/ADM-19495/forum/models/base.py", line 142, in _init_
self.reset_original_state(kwargs.keys())
File "/opt/python/domains/atlassian.com/answers/ADM-19495/forum/models/base.py", line 148, in reset_original_state
self._original_state.update(dict([(f, None) for f in reset_fields]))
File "/opt/python/domains/atlassian.com/answers/ADM-19495/forum/models/base.py", line 155, in _as_dict
([f.attname for f in self._meta.fields] + [k for k in self.__dict__.keys() if k.endswith('_dencache_')])
File "/opt/python/domains/atlassian.com/answers/lib/python2.6/site-packages/django/db/models/fields/subclassing.py", line 96, in _get_
return obj._dict_[self.field.name]

Full backtrace with local variables:

File "/opt/python/domains/atlassian.com/answers/lib/python2.6/site-packages/django/db/models/query.py", line 300, in iterator
yield obj

Arguments: iterator(self=<forum.models.node.NodeQuerySet object at 0x130e5d10 (really long repr)>)
Local variables:

{'aggregate_select': [],
'aggregate_start': 20,
'compiler': <django.db.models.sql.compiler.SQLCompiler object at 0x12c0f890>,
'db': 'default',
'extra_select': ['ranking'],
'fields': [<django.db.models.fields.AutoField object at 0x12761690>,
<django.db.models.fields.CharField object at 0x12765090>,
<django.db.models.fields.CharField object at 0x127650d0>,
<django.db.models.fields.related.ForeignKey object at 0x12765110>,
<django.db.models.fields.TextField object at 0x12765250>,
<django.db.models.fields.CharField object at 0x12758c50>,
<django.db.models.fields.related.ForeignKey object at 0x12758e90>,
<django.db.models.fields.related.ForeignKey object at 0x12758f50>,
<django.db.models.fields.DateTimeField object at 0x12758fd0>,
<django.db.models.fields.IntegerField object at 0x12761050>,
<django.db.models.fields.TextField object at 0x12761090>,
<django.db.models.fields.related.ForeignKey object at 0x127610d0>,
<django.db.models.fields.related.ForeignKey object at 0x12761150>,
<django.db.models.fields.DateTimeField object at 0x127611d0>,
<django.db.models.fields.related.OneToOneField object at 0x12761310>,
<forum.models.utils.PickledObjectField object at 0x127613d0>,
<django.db.models.fields.related.ForeignKey object at 0x12761410>,
<django.db.models.fields.IntegerField object at 0x12761490>,
<django.db.models.fields.BooleanField object at 0x127614d0>],
'fill_cache': False,
'i': 0,
'index_start': 1,
'k': 'ranking',
'load_fields': [],
'max_depth': 5,
'model': <class 'forum.models.question.Question'>,
'obj': <Question: Is it possible to watch a page tree in Confluence>,
'only_load': {},
'pk_idx': 0,
'requested': None,
'row': (12,
3258,
u'Is it possible to watch a page tree in Confluence',
u'confluence',
890,
u'<p>I could not get a way to watch a page tree in Confluence.</p>\r\n<p>This post relates to unanswerd question in <a href="http://forums.atlassian.com/thread.jspa?threadID=54432">http://forums.atlassian.com/thread.jspa?threadID=54432</a></p>',
u'question',
None,
None,
datetime.datetime(2011, 7, 18, 2, 10, 46, 111947),
0,
u'',
10069,
51,
datetime.datetime(2011, 7, 18, 3, 50, 22, 821366),
4329,
None,
None,
46,
False),
'self': [<Question: "An unknown error occured while adding you as watcher">, <Question: How to get shared filters using SOAP API?>, <Question: Active Directory group members do not update after AD changes>, <Question: How would I copy values between custom field contexts automatically?>, <Question: Completely remove redundant plugins?>, <Question: Adding a Global Transition to a Jira workflow doesn't allow 'Return to Step'>, <Question: Why can't I get a Confluence 4 page using the SOAP API?>, <Question: what does this mean: "connection not cleared from thread local">, <Question: Export spaces vua command line(using SOAP remote API) times out>, <Question: Display Sub-task custom fields on Parent Issue>, <Question: Can our existing user license (500-user) be used for two instances?>, <Question: How to use the crowd REST API>, <Question: How do you migrate issues from one Jira Instance to another Jira instance?>, <Question: Display issue status text of linked issues on main issue>, <Question: some way to paste HTML in Confluence 4?>, <Question: Control of wiki home page>, <Question: jQuery 1.6>, <Question: json-rpc not working at all!>, <Question: Invoke embedded-crowd login>, <Question: UWC Export problem using Mediwiki 1.13.4 with Postgresql 8.4>, '...(remaining elements truncated)...'],
'skip': None}

File "/opt/python/domains/atlassian.com/answers/ADM-19495/forum/models/base.py", line 142, in _init_
self.reset_original_state(kwargs.keys())

Arguments: _init_(self=<Question: Whats the difference between the ADMINISTER and SYSTEM_ADMIN permission in JIRAs API?>, *args=<tuple object at 0x1aa59a10 (really long repr)>, **kwargs={})
Local variables:

{'args': (310,
u'Whats the difference between the ADMINISTER and SYSTEM_ADMIN permission in JIRAs API?',
u'jira jira-development',
97,
u'<p>Whats the difference between the <a href="http://docs.atlassian.com/jira/latest/com/atlassian/jira/security/Permissions.html#ADMINISTER">ADMINISTER</a> and <a href="http://docs.atlassian.com/jira/latest/com/atlassian/jira/security/Permissions.html#SYSTEM_ADMIN">SYSTEM_ADMIN</a> permission in JIRAs API?</p>',
u'question',
None,
None,
datetime.datetime(2011, 5, 31, 21, 32, 15, 725828),
1,
u'',
None,
925,
datetime.datetime(2011, 7, 19, 6, 51, 4, 589086),
407,
None,
None,
159,
False),
'kwargs': {},
'self': <Question: Whats the difference between the ADMINISTER and SYSTEM_ADMIN permission in JIRAs API?>}

File "/opt/python/domains/atlassian.com/answers/ADM-19495/forum/models/base.py", line 148, in reset_original_state
self._original_state.update(dict([(f, None) for f in reset_fields]))

Arguments: reset_original_state(self=<Question: Whats the difference between the ADMINISTER and SYSTEM_ADMIN permission in JIRAs API?>, reset_fields=[])
Local variables:

{'reset_fields': [], 'self': <Question: Whats the difference between the ADMINISTER and SYSTEM_ADMIN permission in JIRAs API?>}

File "/opt/python/domains/atlassian.com/answers/ADM-19495/forum/models/base.py", line 155, in _as_dict
([f.attname for f in self._meta.fields] + [k for k in self.__dict__.keys() if k.endswith('_dencache_')])

Arguments: _as_dict(self=<Question: Whats the difference between the ADMINISTER and SYSTEM_ADMIN permission in JIRAs API?>)
Local variables:

{'f': <django.db.models.fields.BooleanField object at 0x127614d0>, 'k': 'id', 'name': 'marked', 'self': <Question: Whats the difference between the ADMINISTER and SYSTEM_ADMIN permission in JIRAs API?>}

File "/opt/python/domains/atlassian.com/answers/lib/python2.6/site-packages/django/db/models/fields/subclassing.py", line 96, in _get_
return obj._dict_[self.field.name]

Arguments: _get_(self=<django.db.models.fields.subclassing.Creator object at 0x127616d0>, obj=<Question: Whats the difference between the ADMINISTER and SYSTEM_ADMIN permission in JIRAs API?>, type=<class 'forum.models.question.Question'>)
Local variables:

{'obj': <Question: Whats the difference between the ADMINISTER and SYSTEM_ADMIN permission in JIRAs API?>, 'self': <django.db.models.fields.subclassing.Creator object at 0x127616d0>, 'type': <class 'forum.models.question.Question'>}