What tell tale signs does Cell Phone Spy Ware leave behind?

3. I have used only Nokia & Sony Ericsson smart phones. So, I know that there is an application control panel (like the one we have on Windows Explorer) that has the list of applications installed. You might want to check it too.
4. You can have a computer turned into a wap gateway and have the traffic of the cell phone diverted through that gateway which will of-course be monitored for any attempts made to connect to the outside world.
5. If possible, install a good phone antivirus and have it scanned.
6. If there is a data card/storage card on the phone, remove it and have it checked on a computer for suspicious files.

Have you considered that she may have installed *flexispy?*
Something like F-Secure may help:
http://www.f-secure.com/v-descs/flexispy_a.shtml

Flexispy fought back by calling F-Secure *malware*
http://www.flexispy.com/remove-fsecure-malware.htm

Symptoms to look out for (in general)

#You experience trouble when shutting off your phone. It seems to just sit there when you try to power down.
#You phone continues to stay lit up for several seconds to a minute after you've shut it off.
#You notice that your phone will light up when you're not using it to make a call, or when no one is calling you, or when you're not using any of the phone's apps. Spyware has to "call" your phone to get information.
#You hear strange background noises or clicks when you're on a call.
#You notice an increase in GPRS activity. This indicates spyware is tracking your location.
#You notice the icon that shows the internet connection activates several times a day for no reason. Again, spyware is gathering information.
#Your phone bill lists many more text messages than you remember sending.
#Your partner or someone else close to you has borrowed your phone to install a software program they say you'll like, or a wallpaper, or a ringtone.
#You let a stranger borrow your phone to make an "emergency" call. The number they called most likely installed spyware on your phone. This is commonly used to set up a program to send large numbers of text messages to your phone for which you are charged.

I do agree that installing AV in mobile can detect "recognised" spyware but for other like Mobile spyware (from Cellular-Spy.com, etc), it need not necessary be flagged as spyware. It will really goes down to identifying the signs.  

With regards to cell phone forensic, there are a number of good professional contact to approach for further advice as well (check out Cellebrite)
http://www.forensickb.com/2008/11/my-current-impression-of-cell-phone.html