IPhone 4s text messages still appear in iPhone search results after being deleted

Apple does not search for very old text messages as it makes the search much slower. There is no setting to modify the period of messages it should go through, but if you really need this then you can jailbreak and SSH into your iPhone. You can then edit the .plist file and make it search for messages that are even 2 years old.

Note: This will significantly make the searching slow.

This is, unfortunately, a limitation of Google Voice. Google Voice cannot spoof your friends' numbers, so it has to send texts from its own numbers. However, each of your contacts will have a unique number from which Voice will send you texts, so you can send messages to those numbers and reply to them and it will reach your friends.

There are two ways around this. You can use the Google Voice app. Messages will come through your data plan and not your SMS plan, and they'll show up with the right names and everything. Alternatively, you can add the numbers Google uses as the "from" address as another number in your iPhone contacts. The number will still work to reach them, and the messages will appear to come from your Google Voice number.