Is it possible to retrieve (accidentally) deleted notes on iPhone 3Gs?

Not in the iPhone itself. If you sync your Notes to Mail (Mac OS X) or Outlook (Windows) then you can find them there. Else, if you synced after creating the note, before deleting it, and have not synced since deleting it, it should be in your iPhone's backup. To get it, you'd need Restore your iPhone from that backup (eliminating newer items, of course), or extract it from the backup with iPhone Backup Extractor (Mac only) or MobileSyncBrowser (Mac/Win).

If you have Mobile Me chat with the MMe tech support team as they may have them in a cache and be able to return them to you.
Good luck