Problem: When in my blog housed on a IIS 7.5 server, I would get an â€œSorry, the page of your requested could not be found, or no longer exists.â€ I thought it was a permalinks issue because when I turned them off, it would work.
Solution: Turned out it was a combination of many things: Permalinks, theme and IIS. Once I changed the theme, I no longer got the error. The theme/permalinks for the theme works on an Apache server but not on IIS. So the solution for now was to change the theme and get with the theme developers to figure out a solution.