I read a letter from the Prime Minister to another MP on some website, and I want to read the MPs letter in response (if there was one). Is there a database of letters that MPs send to each other? I'm assuming these things are public, but I've searched and I can't find any.
No; your assumption that such letters are public is mistaken. There's no statutory requirement to publish correspondence between MPs. Although the House of Commons is a public body under the Freedom of Information Act, individual MPs are not, and thus there's no legislative framework to compel them to publish correspondence. Individual MPs, particularly if they are government ministers, may and do choose to publish correspondence, but it's entirely at their discretion.
They are in an envelope and private unless published. Civil service email is also generally private.
Correspondance guidelines, other than basic FOI and environment FOI acts, if there are any, are given by the whips and party communications staff. Rees Mogg started his current post by issuing strict instructions for correspondance etiquette.