On other thing to try: Once the truck is up to full temp. Take a can of canned air (make sure it is nonflammable), turn it up-side down and spray the O2 sensor. The sudden cold shock may loosen the rust. I believe CRC also makes a freezing spray that does the same thing.
